+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Sophie Germain Primes (/thread-5912.html)
Sophie Germain Primes - PythonLamer - Oct-27-2017
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))
breakSo 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?
RE: Sophie Germain Primes - heiner55 - Oct-27-2017
Your algorithm is wrong, because
print(isPrime(5))
results in None instead of true.
RE: Sophie Germain Primes - PythonLamer - Oct-27-2017
(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
RE: Sophie Germain Primes - heiner55 - Oct-27-2017
Sorry,
Your algorithm is still wrong, because
print(isPrime(5))
results in None instead of true.
Maybe the last "return true" is wrong indented.
RE: Sophie Germain Primes - PythonLamer - Oct-27-2017
(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.
RE: Sophie Germain Primes - heiner55 - Oct-28-2017
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).
RE: Sophie Germain Primes - PythonLamer - Oct-28-2017
(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.
RE: Sophie Germain Primes - heiner55 - Oct-28-2017
https://pypy.org/
“If you want your code to run faster, you should probably just use PyPy.” — Guido van Rossum (creator of Python)