Pierpont primes: Difference between revisions
Content added Content deleted
(Added Sidef) |
|||
Line 702: | Line 702: | ||
return s |
return s |
||
end function</lang> |
end function</lang> |
||
=={{header|Python}}== |
|||
{{trans|Go}} |
|||
<lang python>import random |
|||
# Copied from https://rosettacode.org/wiki/Miller-Rabin_primality_test#Python |
|||
def is_Prime(n): |
|||
""" |
|||
Miller-Rabin primality test. |
|||
A return value of False means n is certainly not prime. A return value of |
|||
True means n is very likely a prime. |
|||
""" |
|||
if n!=int(n): |
|||
return False |
|||
n=int(n) |
|||
#Miller-Rabin test for prime |
|||
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9: |
|||
return False |
|||
if n==2 or n==3 or n==5 or n==7: |
|||
return True |
|||
s = 0 |
|||
d = n-1 |
|||
while d%2==0: |
|||
d>>=1 |
|||
s+=1 |
|||
assert(2**s * d == n-1) |
|||
def trial_composite(a): |
|||
if pow(a, d, n) == 1: |
|||
return False |
|||
for i in range(s): |
|||
if pow(a, 2**i * d, n) == n-1: |
|||
return False |
|||
return True |
|||
for i in range(8):#number of trials |
|||
a = random.randrange(2, n) |
|||
if trial_composite(a): |
|||
return False |
|||
return True |
|||
def pierpont(ulim, vlim, first): |
|||
p = 0 |
|||
p2 = 1 |
|||
p3 = 1 |
|||
pp = [] |
|||
for v in xrange(vlim): |
|||
for u in xrange(ulim): |
|||
p = p2 * p3 |
|||
if first: |
|||
p = p + 1 |
|||
else: |
|||
p = p - 1 |
|||
if is_Prime(p): |
|||
pp.append(p) |
|||
p2 = p2 * 2 |
|||
p3 = p3 * 3 |
|||
p2 = 1 |
|||
pp.sort() |
|||
return pp |
|||
def main(): |
|||
print "First 50 Pierpont primes of the first kind:" |
|||
pp = pierpont(120, 80, True) |
|||
for i in xrange(50): |
|||
print "%8d " % pp[i], |
|||
if (i - 9) % 10 == 0: |
|||
print |
|||
print "First 50 Pierpont primes of the second kind:" |
|||
pp2 = pierpont(120, 80, False) |
|||
for i in xrange(50): |
|||
print "%8d " % pp2[i], |
|||
if (i - 9) % 10 == 0: |
|||
print |
|||
print "250th Pierpont prime of the first kind:", pp[249] |
|||
print "250th Pierpont prime of the second kind:", pp2[249] |
|||
main()</lang> |
|||
{{out}} |
|||
<pre>First 50 Pierpont primes of the first kind: |
|||
2 3 5 7 13 17 19 37 73 97 |
|||
109 163 193 257 433 487 577 769 1153 1297 |
|||
1459 2593 2917 3457 3889 10369 12289 17497 18433 39367 |
|||
52489 65537 139969 147457 209953 331777 472393 629857 746497 786433 |
|||
839809 995329 1179649 1492993 1769473 1990657 2654209 5038849 5308417 8503057 |
|||
First 50 Pierpont primes of the second kind: |
|||
2 3 5 7 11 17 23 31 47 53 |
|||
71 107 127 191 383 431 647 863 971 1151 |
|||
2591 4373 6143 6911 8191 8747 13121 15551 23327 27647 |
|||
62207 73727 131071 139967 165887 294911 314927 442367 472391 497663 |
|||
524287 786431 995327 1062881 2519423 10616831 17915903 18874367 25509167 30233087 |
|||
250th Pierpont prime of the first kind: 62518864539857068333550694039553 |
|||
250th Pierpont prime of the second kind: 4111131172000956525894875083702271</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |