Print next N prime number

user_14142692 0
Viewed 162

This question was suggested to me by a friend. It goes something like this:- Given two integers i and n, starting from i print the next n prime numbers

Note:- The question is asking for the next n prime numbers not and has not specified a range such as i to n.

This is what I came up with, but unfortunately, it's not working. Can you help?

def is_prime(Num):
    prime = True
    if Num > 1:
        for i in range(2, Num):
            if (Num % i) == 0:
                prime = False
        if prime:
            return Num

if __name__ == "__main__":
    startNum = int(input("Enter the first number: "))
    primeNum = int(input("Enter the number of primes you want to print: "))

    primeList = []

    length = len(primeList)

    while length <= primeNum:
        x = is_prime(startNum)
        primeList.append(x)
        startNum = startNum + 1
        length = length + 1

    print(primeList)
    print(x)

The output is as follow

Enter the first number: 3
Enter the number of primes you want to print: 5
[3, None, 5, None, 7, None]
None
primes arrays python
4 Answers

Close. You are adding EVERY return from is_prime to the list, whether it succeeds or fails. Replace your main loop with this:

    while len(primeList) <= primeNum:
        if is_prime(startNum):
            primeList.append(startNum)
        startNum += 1
user_18833160

The problem is that is_prime() only returns a number when Num is prime. When the input is not prime, it returns nothing (i.e., None).

When you append the result of is_prime() to theprimeList you are appending a None value -- as shown in the screenshot.

I suggest changing is_prime() so that it returns either True or False depending on prime, then use this in an if() statement to select between appending a number or not and increasing length accordingly.

user_166014420

If your number of primes to output is very large, it may be more efficient to create a lazy prime generator and add a few parameters to filter/limit its output:

def primes(firstNum=0,count=-1):
    skips = dict() # non-primes to skip
    p,inc = 2,1
    while count:
        if p not in skips:    # p is a new prime (not skipped)
            skips[p*p] = 2*p  # setup skip value for new prime 
            if p>=firstNum:   # filter output to >= firstNum
                yield p
                count -= 1
        else:                         # multiple of a prime, skip p
            stride   = skips.pop(p)   # move skip number forward
            multiple = p + stride  
            while multiple in skips:  # avoid collisions
                multiple += stride    
            skips[multiple] = stride 
        p,inc = p+inc,2               # next potential prime

output:

for p in primes(10,5): print(p)

11
13
17
19
23

The lazy prime generator works by keeping track of numbers that are not prime and should be skipped. Each prime will produce a distinct number to skip, moving over collisions with other primes.

If you don't provide a count to the generator it will never stop generating primes (consuming memory at a rate of one dictionary entry per prime found). The generator is slower than the sieve of Eratosthenes but doesn't require knowing the magnitude of the Nth prime number to be obtained.

user_52375600

This works courtesy of Tim Roberts above.

def is_prime(Num):
    prime = True
    if Num > 1:
        for i in range(2, Num):
            if (Num % i) == 0:
                prime = False
        if prime:
            return Num

if __name__ == "__main__":
    startNum = int(input("Enter the first number: "))
    primeNum = int(input("Enter the number of primes you want to print: "))

    primeList = []

    length = len(primeList)

    while len(primeList) <= primeNum:
        if is_prime(startNum):
            primeList.append(startNum)
        startNum += 1

    print(primeList)

Output:

Enter the first number: 1
Enter the number of primes you want to print: 10
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
user_72383130
Related