0
print("Number of primes must be greater than 2")
number = int(input("Number of primes: "))
if number < 1:
    print("Invalid input")
    exit()
print(2)
print(3)
i = 0
no_primes = 2
while 1 < 2:
    m = 6 * i - 1
    n = 6 * i + 1
    if (2 ** m) % m == 2:
        print(m)
        no_primes += 1
    if no_primes == number:
        break
    if (2 ** n) % n == 2:
        print(n)
        no_primes += 1
    if no_primes == number:
        break
    i += 1

My code uses the fact that primes can be expressed in the form 6n-1 or 6n+1 except for 2 and 3. My while loop looks quite strange but I don't have the expertise to manoeuvre with loops consisting of two variables (no_primes and i in this case). When I generate the first 1000 primes, it skips a few, ending with 7789 instead of 7919. Does anybody know why? Also, sorry if the code looks redundant. If it is, please do state how I can improve it

I started python only a few weeks ago, thought you'll should know

Sergio Tulentsev
  • 226,338
  • 43
  • 373
  • 367
Aqeel
  • 19
  • 2
  • 1
    Why do you use `while 1<2` instead of `while True`? – blackbrandt Aug 03 '21 at 13:49
  • 5
    Can you explain `(2 ** n) % n == 2`? Is this a sufficient condition for n to be a prime? – Kota Mori Aug 03 '21 at 13:49
  • @KotaMori it's a primality test called Fermat's little theorem. Mathematically, it always works. However, it doesn't work properly for large numbers on Pycharm for some reason – Aqeel Aug 05 '21 at 09:04
  • @Aqeel Fermat's little theorem states that if `p` is a prime, it follows that `a**p % p == a`. It does _not_ state the reverse, so if `a**p % p == a` this does not mean `p` is a prime - see 341 as an example. This means your program doesn't print just primes but also Fermat pseudoprimes. – l4mpi Aug 05 '21 at 11:31
  • I didn't know that! Thanks @l4mpi – Aqeel Aug 06 '21 at 04:54

2 Answers2

1

I'm not sure checking (2 ** m) % m == 2 and (2 ** n) % n == 2 will give you all prime numbers. Have you compared with a more brute force approach?

print("Number of primes must be greater than 2")
number = int(input("Number of primes: "))
if number < 1:
    print("Invalid input")
    exit()
elif number == 1:
    print(2)
else:
    print(2)
    print(3)
    prime_set = {2,3}
    i = 1
    while len(prime_set) < number:
        m = 6 * i - 1
        n = 6 * i + 1
        if all(m % p != 0 for p in prime_set):
            prime_set.add(m)
            print(m)
        if all(n % p != 0 for p in prime_set):
            prime_set.add(n)
            print(n)
        i+=1

Here the solution edited by @Aqeel for improved Efficiency:

import time
import math
number = int(input("Number of primes: "))
t_0 = time.time()
if number < 1:
    print("Invalid input")
    exit()
elif number == 1:
    print(2)
else:
    print(2)
    print(3)
    primes = [2, 3]
    i = 1
    while len(primes) < number:
        prime_m = True
        prime_n = True
        m = 6 * i - 1
        n = 6 * i + 1
        sqrt_m = math.sqrt(m)
        sqrt_n = math.sqrt(n)
        for prime in primes:
            if prime > sqrt_m:
                break
            if m % prime == 0:
                prime_m = False
                break
        if prime_m:
            print(m)
            primes.append(m)
        if len(primes) == number:
            break
        for prime in primes:
            if prime > sqrt_n:
                break
            if n % prime == 0:
                prime_n = False
                break
        if prime_n:
            print(n)
            primes.append(n)
        i += 1
t_1 = time.time()
print(f"Found %s prime numbers in %ss" % (number, t_1 - t_0))
Tranbi
  • 11,407
  • 6
  • 16
  • 33
  • Your method looks great! Thanks a lot! – Aqeel Aug 03 '21 at 23:11
  • The program works great! I modified the code a bit by making it check all primes in the list of generated primes lesser than or equal to sqrt(m) or sqrt(n), to make it even faster – Aqeel Aug 04 '21 at 09:00
  • Is it really faster? The computation of sqrt in itself takes quite a toll on the cpu. You could however use a polynomial approximation of sqrt... – Tranbi Aug 04 '21 at 09:16
  • I timed my program and it was faster. However, I'll check it out again – Aqeel Aug 04 '21 at 22:54
  • 1
    To generate the first 10000 primes, here are the average timings. Yours - 5.69052624702s Mine - 1.85073590279s As for the code itself, I'm not sure how to share it conveniently, but it's in this site right here - http://pastie.org/p/2szQREFmjSHfJtFNyry7y3 – Aqeel Aug 05 '21 at 08:49
  • Thanks! My intuition was wrong by a large margin... The sqrt() function is indeed much less cpu-intensive than going through a set of that size. :-) If you don't mind I'll include your solution (with minor changes) to my original answer for archive purposes. – Tranbi Aug 05 '21 at 11:02
0

The answer to your issue is that you are printing non-prime numbers.

Running your code (with input 1000) provides 1000 numbers, but checking these numbers with a proper is_prime() function yields these numbers that are not primes:

341
1105
1387
1729
2047
2465
2701
2821
3277
4033
4369
4681
5461
6601

As answered by @Tranbi, (2 ** m) % m == 2 is not a proper test for testing primes. Check out this answer for a better solution

Almog-at-Nailo
  • 1,152
  • 1
  • 4
  • 20