Member Avatar for trips.dude

Hi All,

I am new to the programming world. I was just writing this code 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 doesnt 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
print (i)
else:
k = k-1

i=i+1

  • 4 Contributors
  • 5 Replies
  • 17K Views
  • 3 Months Discussion Span
  • Latest Post Latest Post by samvinogar

Dani AI

Generated

You are mixing up two tasks: generating primes up to a value N vs. generating the first N primes. For the latter, iterate candidates until you have collected N primes, rather than looping exactly N times. Also, note the first 7 primes are 2, 3, 5, 7, 11, 13, 17 (not 19).

A simple and fast approach is to test each odd candidate for divisibility only by primes found so far, up to sqrt(candidate). This avoids unnecessary work and scales much better than dividing by every integer.

import math

def first_n_primes(n):
    if n <= 0:
        return []
    primes = [2]
    candidate = 3
    while len(primes) < n:
        limit = math.isqrt(candidate)  # use int(math.sqrt(...)) if on older Python
        for p in primes:
            if p > limit:
                primes.append(candidate)
                break
            if candidate % p == 0:
                break
        else:
            primes.append(candidate)  # handles candidate=3 when primes=[2]
        candidate += 2  # skip even numbers
    return primes[:n]

For large N, a Sieve of Eratosthenes is faster. To get the first N primes with a sieve, estimate an upper bound for the Nth prime (e.g., for n >= 6, p_n <= n(log n + log log n)), sieve up to that bound, then take the first N primes. See Sieve of Eratosthenes and the nth-prime bounds from the Prime Number Theorem. Python’s math.isqrt is documented here: math.isqrt.

Recommended Answers

All 5 Replies

Member Avatar for lukerobi

Welcome to the forums! For the future, please use the code tags around your script to make it easier to read :) (http://www.daniweb.com/forums/announcement114-3.html)

This does look like a homework question, so please read the rules about posting homework questions here: http://www.daniweb.com/forums/announcement114-2.html

Here is an example for comming up with prime numbers (up to 1230):

I commented to show you the logic I used, and how it's done..

>>> def getprimes(x):
	primes = []

	# Loop through 9999 possible prime numbers
	for a in range(1, 10000):

		# Loop through every number it could divide by
		for b in range(2, a):

			# Does b divide evenly into a ?
			if a % b == 0:
				break

		# Loop exited without breaking ? (It is prime)
		else:
			# Add the prime number to our list
			primes.append(a)

		# We have enough to stop ?
		if len(primes) == x:
			return primes
		
>>> getprimes(5)
[1, 2, 3, 5, 7]
>>> getprimes(7)
[1, 2, 3, 5, 7, 11, 13]

Another cool way of doing this (and because i like complicated lists):

>>> [p for p in [a for a in range(1,1000) if all([(a % b != 0) for b in range(2, a)])][:input('How many prime numbers? ')]]
How many prime numbers? 10
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23]
>>>

That way is slower because it will allways create a full list of prime numbers (169 of them) and then just give you the ones you ask for... But its fun to work out loops like that :)

Edited by lukerobi because: n/a
Member Avatar for trips.dude

Thank you for sharing your logic. I was just wondering whats going wrong in my logic. So if you could help me in correcting my logic will be really helpful for learners like me.

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
Member Avatar for vegaseat

If you put the number of primes you want, you called it x, in the outer loop range() you will get x numbers, but since not all of them are prime it will print less than x numbers.

You need to make the outer loop an endless loop with a counter and an exit condition to break out of the outer loop ...

i=1
x = int(input("Enter the number:"))

counter = 0
while True:
    c=0;
    for j in range (1, (i+1), 1):
        a = i%j
        if (a==0):
            c = c+1

    if (c==2):
        print (i)
        counter = counter + 1
        if counter >= x:
            break

    i=i+1

BTW, your coding style could be improved, but it's readable enough.

A note to lukerobi, 1 is not a prime number.

Edited by vegaseat because: 1
commented: what is c for? +0
Member Avatar for trips.dude

superb!!!! thanks man

Member Avatar for samvinogar

Thanks very much dude. You rocks

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.