We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #58: Spiral primes
  4. Discussions

Project Euler #58: Spiral primes

  • vidush_rk11
     + 0 comments

    1)Miller Rabin is god
    2) Rest can be done using generalising the corner terms in spiral and using a while loop for increasing side by 2 till the req result in achieved.
    3) I also searched for any hints in ulam spiral, for any pattern, but couldn't find any. 

    import random

def isprime(n):
    '''Miller rabbin'''
    if n in [2,3,5,7]:
        return True
    
    d=n-1
    s=0
    while not d%2:
        s+=1
        d=d//2
    for i in range(4):
        a=random.randint(2,n-1)
        x=pow(a,d,n)
        if x not in [1,n-1]:
            active=True
            for r in range(s):
                if pow(x,2**r,n) == n-1:
                    active=False
                    break
            if active:
                return False
    return True

        
            
n=int(input())
primes_count=0
i=3
last_no=1

while True:
    for j in range(4):
        last_no+=i-1
        if j!=3 and isprime(last_no):
            primes_count+=1
    
    primes_percentage=primes_count/(1+2*(i-1))*100
    if primes_percentage<n:
        print(i)
        break
    i+=2