To find first N prime numbers in python

Question

Hi All,

I am new to the programming world. I was just writing this code in python to generate N prime numbers. User should input the value for N which is the total number of prime numbers to print out. I have written this code but it doesn't throw the desired output. Instead it prints the prime numbers till the Nth number. For eg.: User enters the value of N = 7. Desired output: 2, 3, 5, 7, 11, 13, 19 Actual output: 2, 3, 5, 7

Kindly advise.

i=1
x = int(input("Enter the number:"))
for k in range (1, (x+1), 1):
    c=0
    for j in range (1, (i+1), 1):
        a = i%j
        if (a==0):
            c = c+1

    if (c==2):
          print (i)
    else:
          k = k-1

    i=i+1

Answer 1

The line k = k-1 does not do what you think. It has no effect. Changing k does not affect the loop. At each iteration, k is assigned to the next element of the range, so any changes you have made to k inside the loop will be overwritten.

Answer 2

This code is very confused, and I can't figure out exactly what you were thinking when you wrote it or what you were attempting to accomplish. The first thing I would suggest when trying to figure out how to code is to start by making your variable names extremely descriptive. This will help you get the ideas of what you're doing straight in your head, and it will also help anyone who's trying to help you show you how to get your ideas straight.

That being said, here is a sample program that accomplishes something close to the goal:

primewanted = int(input("This program will give you the nth prime.\nPlease enter n:"))
if primewanted <= 0:
    print "n must be >= 1"
else:
    lastprime = 2 # 2 is the very first prime number
    primesfound = 1  # Since 2 is the very first prime, we've found 1 prime
    possibleprime = lastprime + 1 # Start search for new primes right after
    while primesfound < primewanted:
        # Start at 2.  Things divisible by 1 might still be prime
        testdivisor = 2
        # Something is still possibly prime if it divided with a remainder.
        still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # (testdivisor + 1) because we never want to divide a number by itself.
        while still_possibly_prime and ((testdivisor + 1) < possibleprime):
            testdivisor = testdivisor + 1
            still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # If after all that looping the prime is still possibly prime,
        # then it is prime.
        if still_possibly_prime:
            lastprime = possibleprime
            primesfound = primesfound + 1
        # Go on ahead to see if the next number is prime
        possibleprime = possibleprime + 1
    print "This nth prime is:", lastprime

This bit of code:

        testdivisor = 2
        # Something is still possibly prime if it divided with a remainder.
        still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # (testdivisor + 1) because we never want to divide a number by itself.
        while still_possibly_prime and ((testdivisor + 1) < possibleprime):
            testdivisor = testdivisor + 1
            still_possibly_prime = ((possibleprime % testdivisor) != 0)

could possibly be replaced by the somewhat slow, but possibly more understandable:

        # Assume the number is prime until we prove otherwise
        still_possibly_prime = True
        # Start at 2.  Things divisible by 1 might still be prime
        for testdivisor in xrange(2, possibleprime, 1):
            # Something is still possibly prime if it divided with a
            # remainder.  And if it is ever found to be not prime, it's not
            # prime, so never check again.
            if still_possibly_prime:
                still_possibly_prime = ((possibleprime % testdivisor) != 0)

Answer 3

using a regexp :)

#!/usr/bin/python

import re, sys


def isPrime(n):
    # see http://tinyurl.com/3dbhjv
    return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None


N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100              # upper-bound of search space
l = list()           # result list

while len(l) < N:
    l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
    M += 100                                # increment upper-bound

print l[:N] # print result list limited to N elements

Answer 4

Hi, What you need is a Prime Sieve (a fast type of algorithm for finding primes), a very simple one is Sieve of Eratosthenes (check wikipedia) and here is an implementation in PHP http://www.scriptol.com/programming/sieve.php

Answer 5

What you want is something like this:

x = int(input("Enter the number:"))
count = 0
num = 2
while count < x:
     if isnumprime(x):
        print x
        count = count + 1
     num = num + 1

I'll leave it up to you to implement "isnumprime()". ;) Hint: You only need to test division with all previously found primenumbers.

Answer 6

Until we have N primes, take natural numbers one by one, check whether any of the so-far-collected-primes divide it.

If none does, "yay", we have a new prime...

that's it.

>>> def generate_n_primes(N):
...     primes  = []
...     chkthis = 2
...     while len(primes) < N:
...         ptest    = [chkthis for i in primes if chkthis%i == 0]
...         primes  += [] if ptest else [chkthis]
...         chkthis += 1
...     return primes
...
>>> print generate_n_primes(15)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Answer 7

Using generator expressions to create a sequence of all primes and slice the 100th out of that.

from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
print("100th prime is %d" % next(islice(primes, 99, 100)))

Answer 8

For reference, there's a pretty significant speed difference between the various stated solutions. Here is some comparison code. The solution pointed to by Lennart is called "historic", the one proposed by Ants is called "naive", and the one by RC is called "regexp."

from sys import argv
from time import time

def prime(i, primes):
    for prime in primes:
        if not (i == prime or i % prime):
            return False
    primes.add(i)
    return i

def historic(n):
    primes = set([2])
    i, p = 2, 0
    while True:
        if prime(i, primes):
            p += 1
            if p == n:
                return primes
        i += 1

def naive(n):
    from itertools import count, islice
    primes = (n for n in count(2) if all(n % d for d in range(2, n)))
    return islice(primes, 0, n)

def isPrime(n):
    import re
    # see http://tinyurl.com/3dbhjv
    return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None

def regexp(n):
    import sys
    N = int(sys.argv[1]) # number of primes wanted (from command-line)
    M = 100              # upper-bound of search space
    l = list()           # result list

    while len(l) < N:
        l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
        M += 100                                # increment upper-bound

    return l[:N] # print result list limited to N elements

def dotime(func, n):
    print func.__name__
    start = time()
    print sorted(list(func(n)))
    print 'Time in seconds: ' + str(time() - start)

if __name__ == "__main__":
    for func in naive, historic, regexp:
        dotime(func, int(argv[1]))

The output of this on my machine for n = 100 is:

naive
[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]
Time in seconds: 0.0219371318817
historic
[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]
Time in seconds: 0.00515413284302
regexp
[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]
Time in seconds: 0.0733318328857

As you can see, there's a pretty big discrepancy. Here it is again for 1000 (prime outputs removed):

naive
Time in seconds: 1.49018788338
historic
Time in seconds: 0.148319005966
regexp
Time in seconds: 29.2350409031

Answer 9

Super quick sieve implementation - takes 0.146s for the first 1000 primes on my PC:

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

primes = gen_primes()


x = set()
y = 0
a = gen_primes()
while y < 10000:
  x |= set([a.next()])
  y+=1

return sorted(x)

Answer 10

how can i make a calculator in python