CODEWITHSUNDEEP
python
Jake
Jake

Reputation: 11

Finding Prime numbers- what am I doing wrong?

I'm trying to generate a certain number(input) of prime numbers, only using "while" "for" and "If",etc statements. for example, if I input "8", the program should return 8 prime numbers 2,3,5,7,11,...and so on.

below is my code, but it only seems to give me 2 and 3, no matter what number I input.

Thank you so much for all your help!

num=input("enter the number of prime numbers needed:")
if num=='0' or num=="" or int(num)<0:
    print("No data ^^")
else:
    num=int(num)
    i=2; N=3; prm=True
    print(2); count=1
    while(True):
        if count==num:
            break
        i=2
        while i<N:
            if N%i==0:
                prm=False
                break
            else:
                i+=1
        if prm==True:
            print(N); count+=1
        N+=1

Upvotes: 1

Views: 79

Answers (3)

Eric Jin
Eric Jin

Reputation: 3924

Try this. It runs a whole lot faster.

factor = lambda x: [i for i in range(1,x+1) if x % i == 0]
isprime = lambda x: True if len(factor(x)) == 2 else False

num = input('enter number of primes : ')
if num == '' or int(num) <= 0:
    print('No data ^^')

else:
    num = int(num)
    primes = []
    for i in range(2, 115792089237316195423570985008687907853269984665640564039457584007913129639936):
        if i not in (2, 3) and i % 6 not in (1, 5):
            continue
        if isprime(i):
            primes.append(i)
            if len(primes) >= num:
                break

print(primes)

Explanation

The isprime() function finds if a number is prime by checking if the number has two factors. The factor() function iterates through the numbers [1, x] and returns every number that has a modulo value of 0, meaning that it is a factor of x. (lambda functions)

Then I loop through starting from 1 (the upper cap is 2^256) and check if it is prime. A quick check is that a prime number >3 must be congruent to 1 or 5 modulo 6 (2,4 are even, 3 is divisible by 3) If it is I add it to the list of primes, and ONLY if it is, check to break from the loop. This increases the speed a ton.

Example output

enter number of primes : 150
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863]

Timings

First 1000 primes: 1 second

First 2000 primes: 4 seconds

First 3000 primes: 10 seconds

First 4000 primes: 20 seconds

First 5000 primes: 33 seconds

By the way, 17389 is the 2000th prime.

Upvotes: 0

Karl Knechtel
Karl Knechtel

Reputation: 61557

The intended logic is that for each candidate value, we start out assuming it's prime, then do each check to find out if it isn't.

Therefore, prm = True should be set at the beginning of each of the loops used to test a candidate value. In the existing code, it's set only once, outside the while loop. Thus, the first time that a composite value is found, prm gets set to False - and can never be set True again, therefore no more primes are detected.

Upvotes: 0

Sven
Sven

Reputation: 1127

you just forgot to add prm = true at the end of the loop:

num=input("enter the number of prime numbers needed:")
if num=='0' or num=="" or int(num)<0:
    print("No data ^^")
else:
    num=int(num)
    i=2; N=3; prm=True
    print(2); count=1
    while(True):
        if count==num:
            break
        i=2
        while i<N:
            if N%i==0:
                prm=False
                break
            else:
                i+=1
        if prm==True:
            print(N); count+=1
        N+=1
        prm=True

Btw. The Code you wrote isn't the cleanest, maybe you should work on that

Upvotes: 1

Related Questions