1
start = 100000000
end = 100000050
for i in range(start, end+1):
    if i > 100000000:
        for j in range(2, i):
            if isinstance(i**0.5, int) or (i % j == 0):
             break
        else:
            print(i)

I'm new to python and I'm trying to find the first prime number bigger than 100 million. I need to figure out how to make it run faster.

D A
  • 3,130
  • 4
  • 25
  • 41
Kai Broadbent
  • 11
  • 4
  • 3
    Well for starters `range(2, i)` is looping through 100 million integers. That's going to be slow – Wondercricket Dec 09 '21 at 16:51
  • 1
    Why do you need the `if` statement? Why not just set `start = 100000001`? – Barmar Dec 09 '21 at 16:51
  • 3
    `isinstance(i**0.5, int)` will never be true. Raising to a fractional power always returns a float, even if `i` is a perfect square. – Barmar Dec 09 '21 at 16:53
  • @Wondercricket It only has to loop through all 100 million integers when the number is prime. Otherwise, it stops when it finds the first factor. – Barmar Dec 09 '21 at 16:55
  • 1
    You can improve the inner loop with `range(2, int(i**0.5)+1)` – Barmar Dec 09 '21 at 16:56
  • 5
    [This more general primes thread](https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n) on SO might be relevant. – D A Dec 09 '21 at 17:02
  • which one is the inner loop ? – Kai Broadbent Dec 09 '21 at 17:08
  • thank you @Barmar it runs a lot faster but I can't make it give me Just the One Prime bigger than 100 million I can't make it stop unless I manually reset the end to be one greater than the prime number but I I kind of want it so that it gives it to me without me forcing it to you know and I want to make it more robust – Kai Broadbent Dec 09 '21 at 17:26
  • You have to break out of the outer loop when the inner loop finds a prime. – Barmar Dec 09 '21 at 17:26
  • well I need to do is have it stopped after a prints once that has been the biggest problem so far – Kai Broadbent Dec 09 '21 at 17:27
  • The inner loop is `for j`, the outer loop is `for i` – Barmar Dec 09 '21 at 17:29
  • plain trial division is the slower way possible to check if a given number, specially a big one, is prime or not. You need a more powerful test like the [Miller-Rabin test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test). Relevant [numberphile video](https://www.youtube.com/watch?v=_MscGSN5J6o) – Copperfield Dec 09 '21 at 17:37

1 Answers1

0

If you only want to find the first prime, break out of the outer loop when the inner loop finds a prime.

start = 100000001
end = 100000050
for i in range(start, end+1):
    for j in range(2, int(i ** 0.5)+1):
        if (i % j == 0):
            break # stop inner loop
    else:
        print(i)
        break # stop outer loop
else:
    print("No prime found")
Barmar
  • 741,623
  • 53
  • 500
  • 612