To find first N prime numbers in python

Question

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 example: 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):
    c = 0
    for j in range(1, i+1):
        a = i % j
        if a == 0:
            c = c + 1

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

    i = i + 1

Answer 1

using a regexp :)

#!/usr/bin/python

import re, sys


def isPrime(n):
    # see http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
    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 2

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 3

Super quick sieve implementation by David Eppstein - 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

print "x contains {:,d} primes".format(len(x))
print "largest is {:,d}".format(sorted(x)[-1])

Answer 4

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 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 += 1
     num += 1

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

Answer 6

Here's what I eventually came up with to print the first n primes:

numprimes = raw_input('How many primes to print?  ')
count = 0
potentialprime = 2

def primetest(potentialprime):
    divisor = 2
    while divisor <= potentialprime:
        if potentialprime == 2:
            return True
        elif potentialprime % divisor == 0:
            return False
        while potentialprime % divisor != 0:
            if potentialprime - divisor > 1:
                divisor += 1
            else:
                return True

while count < int(numprimes):
    if primetest(potentialprime) == True:
        print 'Prime #' + str(count + 1), 'is', potentialprime
        count += 1
    potentialprime += 1

Answer 7

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 8

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 9

def isPrime(y):
  i=2
  while i < y:
    if y%i == 0 :
      return 0
      exit()
    i=i+1
  return 1

x= raw_input('Enter the position 1st,2nd,..nth prime number you are looking for?: ')
z=int(x)
# for l in range(2,z)
count = 1
n = 2
while count <= z:
  if isPrime(n) == 1:
    if count == z:
      print n
    count +=1
  n=n+1

Answer 10

You can take the number of prime number inputs. As per your method I have taken here a predefined count of 10:

i = 2
if i == 2:
    print(str(i) + "is a prime no")
    i = i+1
c=1

while c<10:
    for j in range(2, i):
        if i%j==0:
            break

    if i == j+1:
        print(str(i) + "is aa prime no")
        c=c+1

    i=i+1

Answer 11

Fastests

import math

n = 10000 #first 10000 primes
tmp_n = 1
p = 3
primes = [2]

while tmp_n < n:

    is_prime = True
    for i in range(3, int(math.sqrt(p) + 1), 2):
        # range with step 2

        if p % i == 0:
            is_prime = False

    if is_prime:
        primes += [p]
        tmp_n += 1

    p += 2

print(primes)

Answer 12

n=int(input("Enter the number:: "))

for i in range(2,n):
    p=i
    k=0
    for j in range(2,p-1):
        if(p%j==0):
            k=k+1
    if(k==0):
        print(p)

Answer 13

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 14

This might help:

import sys
from time import time
def prime(N):
    M=100
    l=[]
    while len(l) < N:
        for i in range(M-100,M):    
            num = filter(lambda y :i % y == 0,(y for y in range(2 ,(i/2)))) 
            if not num and i not in [0,1,4]:
                l.append(i)
        M +=100
    return l[:N]


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


if __name__ == "__main__":
    dotime(prime, int(sys.argv[1]))

Answer 15

Here's a simple recursive version:

import datetime
import math

def is_prime(n, div=2):
    if div> int(math.sqrt(n)): return True
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()

until = raw_input("How many prime numbers my lord desires??? ")
until = int(until)

primelist=[]
i=1;
while len(primelist)<until:
    if is_prime(i):
        primelist.insert(0,i)
        i+=1
    else: i+=1



print "++++++++++++++++++++"
print primelist
finish = datetime.datetime.now()
print "It took your computer", finish - now , "secs to calculate it"

Here's a version using a recursive function with memory!:

import datetime
import math

def is_prime(n, div=2):
    global primelist
    if div> int(math.sqrt(n)): return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now

until = raw_input("How many prime numbers my lord desires??? ")
until = int(until)

primelist=[]
i=1;
while len(primelist)<until:
    if is_prime(i):
        primelist.insert(0,i)
        i+=1
    else: i+=1



print "Here you go!"
print primelist

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"

Hope it helps :)

Answer 16

Try using while loop to check the count, that is easy. Find the code snippet below :

i=1
count = 0;
x = int(input("Enter the number:\n"))
while (count < x):
c=0
for j in range (1, (i+1), 1):
    a = i%j
    if (a==0):
        c = c+1

if (c==2):
      print (i)
      count = count+1
i=i+1

Answer 17

Whilst playing with prime numbers in Python V3 I noticed that the smallest number by which a composite(non-prime) number is divisible is itself always a prime that is less than the square root of the number under test.

Below is my implementation of that finding to calculate the first N prime numbers.

first 1,000 primes in 0.028S | first 10,000 primes in 0.6S | first 100,000 primes in 14.3S

The snippet below also indicates how long the generation took and prints out the primes in a nice table format.

import time
import math

def first_n_Primes(n):
    number_under_test = 4
    primes = [2,3]
    while len(primes) < n:
        check = False
        for prime in primes:
            if prime > math.sqrt(number_under_test) : break
            if number_under_test % prime == 0:
                check = True
                break
        if not check:
            for counter in range(primes[len(primes)-1],number_under_test-1,2):
                if number_under_test % counter == 0:
                    check = True
                    break
        if not check:
            primes.append(number_under_test)
        number_under_test+=1
    return primes

start_time = time.time()
data = first_n_Primes(1000)
end_time = time.time()

i = 1
while i < len(data)+1:
    print('{0: <9}'.format(str(data[i-1])), end="")
    if i%10 == 0: print("")
    i+=1

print("\nFirst %d primes took %s seconds ---" % (len(data),end_time - start_time))

Answer 18

This is my version

import timeit
import math

__author__ = 'rain'


primes = [2]

def is_prime(n):
    for prime in primes:
        if n % prime == 0:
            return False
    return True


def find_nth_prime(n):
    current_index = 0
    while(len(primes) < n):
        if current_index == 0:
            start_value = 3
            end_value = 2 * 2
        else:
            start_value = primes[current_index - 1] * primes[current_index - 1] + 1
            end_value = primes[current_index] * primes[current_index]
        for i in range(start_value, end_value):
            if is_prime(i):
                primes.append(i)
        current_index += 1
    return primes[n-1]


def solve():
    return find_nth_prime(10001)

print solve()

print timeit.timeit(solve, number=10)

I use a sieve to scan primes, it's quite quick

It's take only 3.8e-06 seconds to get 10001th prime (10 times).

Answer 19

Try this:

primeList = []
for num in range(2,10000):
    if all(num%i!=0 for i in range(2,num)):
        primeList.append(num)
x = int(raw_input("Enter n: "))
for i in range(x):
    print primeList[i]

Answer 20

max = input("enter the maximum limit to check prime number");
if max>1 :
    for i in range (2,max):
        prime=0;
        for j in range (2,i):
            if(i%j==0):
                prime=1;
                break
        if(prime==0 and i!=0):
            print(i,"is prime number");
else:
    print("prime no start from 2");

Answer 21

prime=2
counter = 0
x = int(input("Enter the number:\n"))
while (counter < x):
    if all(prime%j!=0 for j in range(2, prime)):
        print(prime, "is a prime number")
        counter+=1


    prime+=1

Answer 22

count = -1
n = int(raw_input("how many primes you want starting from 2 "))
primes=[[]]*n
for p in range(2, n**2):
    for i in range(2, p):
        if p % i == 0:
            break
    else:
        count +=1
        primes[count]= p
        if count == n-1:
            break

print (primes)
print 'Done'

Answer 23

Anwer here is simple i.e run the loop 'n' times.

n=int(input())
count=0
i=2
while count<n:
    flag=0
    j=2
    while j<=int(i**0.5):
        if i%j==0:
            flag+=1
        j+=1
    if flag==0:
        print(i,end=" ")
        count+=1
    i+=1

Answer 24

#!/usr/bin/python3
import sys

primary_numbers = [1, 2]


def is_prime(i):
    for pn in enumerate(primary_numbers[2:]):
        if i % pn[1] == 0:
            return False

    return True

def main(position):
    i = 3
    while len(primary_numbers) < int(position):
        print(i)
        res = is_prime(i)
        if res:
            primary_numbers.append(i)
        i += 2


if __name__ == '__main__':
    position = sys.argv[1]
    main(position)
    print(primary_numbers)

Answer 25

def isprime(n):
    if n <= 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False
    else:
        return True

def list_prime(z):
    y = 0
    def to_infinity():
        index=0
        while 1:
            yield index
            index += 1
    for n in to_infinity():
        if y < z:
            if isprime(n):
                y = y + 1
                print(n, end='\n', flush=True)
        else:break
    print(f'\n {z} prime numbers are as above.')

# put your range below
list_prime(10)

Answer 26

I am not familiar with Python so I am writing the C counter part(too lazy to write pseudo code.. :P) To find the first n prime numbers.. // prints all the primes.. not bothering to make an array and return it etc..

void find_first_n_primes(int n){
   int count = 0;
   for(int i=2;count<=n;i++){
     factFlag == 0; //flag for factor count... 
     for(int k=2;k<sqrt(n)+1;k++){
       if(i%k == 0) // factor found..
        factFlag++;
     }
      if(factFlag==0)// no factors found hence prime..
        {
         Print(i);   // prime displayed..
         count++;
        }
   }
}

Answer 27

This might help:

def in_prime(n):
    p=True
    i=2
    if i**2<=n:
        if n%i==0:
            p=False
            break
    if (p):
        return n

Answer 28

Hi! I am very new to coding, just started 4 days back. I wrote a code to give back the first 1000 prime numbers including 1. Have a look

n=1
c=0
while n>0:
   for i in range(2,n):
      if n%i == 0:
         break
   else:
      print(n,'is a prime')
      c=c+1
   n=n+1
   if c==1000:
      break

Answer 29

#Simple python program to print N prime numbers 

    inp = int(input("required prime numbers"))
    list =set ()
    num =1
    while(1):
      for i in range(2,num):
         if num%i==0:
            #print("not prime")
            break
      else:
          #print("prime")
          list.add(num)    
      if len(list)<inp:
          num=num+1
      else:
          break
    print("n primes:",list)

Answer 30

def Isprime(z):
    '''returns True if the number is prime OTW returns false'''
    if z<1:
        return False
    elif z==1:
        return False

    elif z==2:
        return True 

    else:
        for i in range(2,z):
            if z%i==0:
                return False
            else:
                return True

This is the way I did it. Of course, there are so many ways you can do it.