Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Sophie Germain Primes
#1
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?
Reply
#2
Your algorithm is wrong, because
    print(isPrime(5))
results in None instead of true.
Reply
#3
(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
Reply
#4
Sorry,
Your algorithm is still wrong, because
    print(isPrime(5))
results in None instead of true.

Maybe the last "return true" is wrong indented.
Reply
#5
(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.
Reply
#6
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).
Reply
#7
(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.
Reply
#8
https://pypy.org/

“If you want your code to run faster, you should probably just use PyPy.” — Guido van Rossum (creator of Python)
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Need help to identify Mersenne Primes, I do need a search pattern. Pleiades 0 1,891 Dec-03-2019, 11:05 PM
Last Post: Pleiades
  Convert Vba Primes to Python Primes jackhj 1 2,388 Apr-18-2018, 12:19 AM
Last Post: Larz60+

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020