''' Check Prime Number reference: https://en.wikipedia.org/wiki/Prime_number https://en.wikipedia.org/wiki/Sieve_of_Atkin https://en.wikipedia.org/wiki/Sieve_of_Sundaram https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test ################################### # Author: Lindsay Chen ################################### ''' isPrime_exhaustive = lambda n: all(n%i for i in range(2,n)) import math # Unlike the built-in ** operator, math.pow() converts both its arguments to type float. Use ** or the built-in pow() function for computing exact integer power. isPrime_trial_division = lambda n: all(n%i for i in range(2, int(math.pow(n, 0.5))+1)) from math import log2, log def isPrimeByMillerRabin_Deterministic(n): if n==2: return True s = next((x for x in range(int(log2(n)), 0, -1) if (n-1)%(1<1): if count%2==0: for j in range(count): a.remove(v) else: for j in range(count-1): a.remove(v) # exclude sqaurefree numbers if v in squarefrees: a.remove(v) continue if v in squarefrees: a.remove(v) else: i+=1 #for prime in a: # yield prime ''' # maxium n=45000 withot time limit exceeded for n in a: if a.count(n)%2 and n not in squarefrees: primes.append(n) ''' #print(sorted(primes)) # sorted changed primes into list primes = primes +a #return primes return max(primes), len(primes) def sieveSundaram(limit): # maxium n=7000 withot Memory limit exceeded n = int((limit-2)/2)+1 crossouts = set(i+j+2*i*j for i in range(1, int(n/3)+1) for j in range(i,int(n/3)+1)) allfactors = set(i for i in range(1,n)) factors = allfactors-crossouts #primes = (2,)+tuple(2*i+1 for i in range(1,n) if i not in crossouts) primes = (2,)+tuple(2*i+1 for i in factors) #yield 2 #for i in factors: # yield 2*i+1 #return primes return max(primes), len(primes) #print(sieveEratosthenes(2500)) #print(sievePrimes(5000)) #print(sieveAtkin(50000)) #print(sieveSundaram(5000)) #print(isPrime_trial_division(49277)) print(isPrimeByMillerRabin_Deterministic(11220046602481)) ''' from random import randrange for i in range(5): number = randrange(1,100) print('exhaustive check:', number, exhaustive_check(number)) print('trial division check:', number, trial_division_check(number)) print('Sieve of Eratosthenes, max prime under {}: {}'.format(number, sieveEratosthenes(number))) print() '''

Numbers-Prime Number