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
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
break
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
else:
potentialprime += 1
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
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
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
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'
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]
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 :)
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)
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
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]
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).
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.
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
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
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))
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
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)))
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
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
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)
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]))
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++;
}
}
}
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])
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");
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.
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)
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)
#!/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)
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.
Source: Stackoverflow.com