-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

Henry Ecker
  • 34,399
  • 18
  • 41
  • 57
Mark Gyomory
  • 41
  • 4
  • I see no reason why this code wouldn't end but this will need a lot of patience. – Michael Butscher Dec 19 '21 at 23:57
  • 1
    The `isprime` function is incorrect. It says that 2 isn't a prime. – md2perpe Dec 20 '21 at 00:02
  • you can find faster way to check if a number is prime here : https://stackoverflow.com/questions/4643647/fast-prime-factorization-module – Malo Dec 20 '21 at 00: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. – President James K. Polk Dec 20 '21 at 00: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](https://en.wikipedia.org/wiki/Primality_test). – user229044 Dec 20 '21 at 05:35

1 Answers1

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.

Yevgeniy Kosmak
  • 3,561
  • 2
  • 10
  • 26
  • 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. – Mark Gyomory Dec 20 '21 at 00:08
  • 1
    @MarkGyomory if you are interested, you cab try faster [Miller-Rabin algorithm](https://gist.github.com/Ayrx/5884790), for example, explanation goes [here](https://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes). – Yevgeniy Kosmak Dec 20 '21 at 00:13
  • @MarkGyomory Can plot out execution times as N approaches “too large to time” on a graph .. might not want to wait about. – user2864740 Dec 20 '21 at 00:30
  • 1
    @MarkGyomory do you still need any help with your question? If no, please mark answer as accepted. – Oleksii Tambovtsev Dec 25 '21 at 16:42