CoCalc Public FilesPRIMALITY.sagewsOpen with one click!
Author: Aurélien Ooms
Views : 50
Compute Environment: Ubuntu 18.04 (Deprecated)
from random import randint import heapq
def PRIME ( k , p ) : """ p is odd see ed. 3, p. 401 """ _1 = p - 1 for i in range( k ) : a = randint( 1 , _1 ) if power_mod( a , _1 , p ) != 1 : return False s = _1 while not s & 1 : x = power_mod( a , s , p ) if x != 1 : if x != _1 : return False break s //= 2 return True
def isprime ( p ) : if p <= 1 : return False if p == 2 : return True if not p & 1 : return False d = 2 e = 1 / 2**d a = -log( 4 * e * ( 1 - e ) , 2 ) f = lambda n : n / 8 n = ceil( log( p , 2 ) ) k = int( ceil( f( n ) / a ) ) return PRIME( d * k , p )
n = 1000 primes = primes_first_n( n ) print( primes[:10] )
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
last = primes[-1] primes = set( primes ) last
7919
all( map( isprime , sorted( primes ) ) )
True
composites = set( range( 1 , last ) ) - primes print( heapq.nsmallest( 10 , composites ) )
[1, 4, 6, 8, 9, 10, 12, 14, 15, 16]
not any( map( isprime , sorted( composites ) ) )
True
p = next_prime( 2**1024 ) c = p - 2 print( p )
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859
%time isprime( p )
True CPU time: 2.76 s, Wall time: 2.83 s
%time isprime( c )
False CPU time: 0.00 s, Wall time: 0.00 s
%time p in Primes( )
True CPU time: 5.70 s, Wall time: 5.80 s
%time c in Primes( )
False CPU time: 0.00 s, Wall time: 0.00 s