Looking for a way to optimize this to have it run a bit faster:
#!python3
def isPrime(num):
if num < 2:
return False
if num == 2:
return True
else:
for div in range(2,int(num / 2)):
if num % div == 0:
return False
return True
for i in range(1000000000000000,9999999999999999):
if isPrime(i):
i = (i * 2) + 1
if isPrime(i):
print(int((i - 1) / 2))
break
So a quick background on the code. It tests for safe prime numbers, where p = (p * 2) +1, and where the original p is prime and the calculated p is also prime. An example is 5, because 5 is a prime number and 5*2+1=11, which is also prime.
Does anyone have any suggestions?
Your algorithm is wrong, because
print(isPrime(5))
results in None instead of true.
(Oct-27-2017, 06:58 PM)heiner55 Wrote: [ -> ]Your algorithm is wrong, because
print(isPrime(5))
results in None instead of true.
You're right... I actually just removed the lower digit checks altogether. I used them to check to see if things were working on lower numbers before I set everything up for 16 digit numbers.
so, this is what is needed:
#!python3
def isPrime(num):
for div in range(2,int(num / 2)):
if num % div == 0:
return False
return True
for i in range(1000000000000000,9999999999999999):
if isPrime(i):
i = (i * 2) + 1
if isPrime(i):
print(int((i - 1) / 2))
break
Sorry,
Your algorithm is still wrong, because
print(isPrime(5))
results in None instead of true.
Maybe the last "return true" is wrong indented.
(Oct-27-2017, 07:20 PM)heiner55 Wrote: [ -> ]Sorry,
Your algorithm is still wrong, because
print(isPrime(5))
results in None instead of true.
Maybe the last "return true" is wrong indented.
Yep... it needs to be two spaces back. At any rate... this process for getting sophie germain prime numbers seems to be extremely slow. I'm not quite sure how to speed it up.
If I google for "prime number algorithm", I get a lot of suggestions.
Maybe you should also google.
It is enough to end the for-loop if sqrt(n) instead of n/2.
You could save the result of isPrime(2*i+1), because you need it later again for isPrime(i).
(Oct-28-2017, 03:08 AM)heiner55 Wrote: [ -> ]If I google for "prime number algorithm", I get a lot of suggestions.
Maybe you should also google.
It is enough to end the for-loop if sqrt(n) instead of n/2.
You could save the result of isPrime(2*i+1), because you need it later again for isPrime(i).
That's actually quite a bit faster. Thank you.
https://pypy.org/
“If you want your code to run faster, you should probably just use PyPy.” — Guido van Rossum (creator of Python)