Does Anyone Know Why My Program Doesn't Generate The Correct Amount Of Prime Numbers?

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

Solution 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))

Solution 2:

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