-1

I wanted to write a program that tried to look for these primes. I have run it a few times and when N gets to 25 it does not have an output in over 24 hours. Is this just because it will take a while or because something is wrong with it?

Here is my code:

import time
def isprime(n):
    """
    Assumes that n is a positive natural number
    """
    if n % 2 == 0:
        return False
    i = 3
    # This will loop from 2 to int(sqrt(x))
    while i*i <= n:
        # Check if i divides x without leaving a remainder
        if n % i == 0:
            # This means that n has a factor in between 2 and sqrt(n)
            # So it is not a prime number
            return False
        i += 2
    # If we did not find any factor in the above loop,
    # then n is a prime number
    return True

prime = False
primes = []
n = 0
while n <=1000:
    startTime = time.time()
    num = ''
    n += 1
    for i in range(1,n+1):
        num += str(i)
    for j in reversed(range(1,n)):
        num += str(j)
    prime = isprime(int(num))
    if prime:
        primes.append(num)
        prime = False
    print(f"N{n} took {time.time()- startTime} secounds")

print(primes)

Credit for the isprime function: https://www.rookieslab.com/posts/fastest-way-to-check-if-a-number-is-prime-or-not

5
  • I see no reason why this code wouldn't end but this will need a lot of patience. Dec 19, 2021 at 23:57
  • 1
    The isprime function is incorrect. It says that 2 isn't a prime.
    – md2perpe
    Dec 20, 2021 at 0:02
  • you can find faster way to check if a number is prime here : stackoverflow.com/questions/4643647/…
    – Malo
    Dec 20, 2021 at 0:12
  • Since pow(2, n-1, n) != 1 for n=12345... it is not prime. Furthermore, alperton ecm calculator factors it in a few seconds. Dec 20, 2021 at 0:48
  • The first factor you're going to hit is 989931671244066864878631629. Using your current algorithm, you'll get there in 494965835622033432439315814 iterations (n / 2, because you increment by 2 each loop). If you're doing this on a 3gz processor and it is somehow able to perform exactly one iteration per clock cycle, you'll find this factor in a little over 5 billion years, give or take. Your link implies this is the "fastest method" to check for primality, but if you haven't guessed: it is not.
    – user229044
    Dec 20, 2021 at 5:35

1 Answer 1

4

Well, for n = 25 num would be so:

12345678910111213141516171819202122232425242322212019181716151413121110987654321

So it's totally okay that computing isprime(num) takes a lot of time. Complexity of your algorithm is O(sqrt(num)), so on usual computer that computation has to last long.

4
  • Okay thanks. I was just making sure nothing was broken. I ken it would take awhile just didn't realize how long I guess. Well thanks again. Dec 20, 2021 at 0:08
  • 1
    @MarkGyomory if you are interested, you cab try faster Miller-Rabin algorithm, for example, explanation goes here. Dec 20, 2021 at 0:13
  • @MarkGyomory Can plot out execution times as N approaches “too large to time” on a graph .. might not want to wait about. Dec 20, 2021 at 0:30
  • 1
    @MarkGyomory do you still need any help with your question? If no, please mark answer as accepted. Dec 25, 2021 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.