# Simple prime number generator in Python

Could someone please tell me what I'm doing wrong with this code? It is just printing 'count' anyway. I just want a very simple prime generator (nothing fancy).

``````import math

def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count

count += 1
``````

82

There are some problems:

• Why do you print out count when it didn't divide by x? It doesn't mean it's prime, it means only that this particular x doesn't divide it
• `continue` moves to the next loop iteration - but you really want to stop it using `break`

Here's your code with a few fixes, it prints out only primes:

``````import math

def main():
count = 3

while True:
isprime = True

for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break

if isprime:
print count

count += 1
``````

For much more efficient prime generation, see the Sieve of Eratosthenes, as others have suggested. Here's a nice, optimized implementation with many comments:

``````# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

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
``````

Note that it returns a generator.

Tuesday, June 1, 2021

61

It's not precisely a direct translation of your loops, but it's quite close and compact:

``````>>> l = range(2, 101)
>>> sorted(set(l).difference(a for i in l for a in l if a!=i and a%i == 0))
[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]
``````

Although I'd suggest `a > i` rather than `a != 0` as being shorter and faster ;)

Sunday, August 15, 2021

46

I would actually restructure the program to look like this:

``````for p in range(2, n+1):
for i in range(2, p):
if p % i == 0:
break
else:
print p,
print 'Done'
``````

This is perhaps a more idiomatic solution (using a `for` loop instead of a `while` loop), and works perfectly.

The outer `for` loop iterates through all the numbers from 2 to `n`.

The inner one iterates to all numbers from 2 to `p`. If it reaches a number that divides evenly into `p`, then it breaks out of the inner loop.

The `else` block executes every time the for loop isn't broken out of (printing the prime numbers).

Then the program prints `'Done'` after it finishes.

As a side note, you only need to iterate through 2 to the square root of `p`, since each factor has a pair. If you don't get a match there won't be any other factors after the square root, and the number will be prime.

Thursday, September 23, 2021

35

Let's do some equational reasoning.

``````primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
``````

The `[2..]` is sintactic sugar for `[2, 3, 4, 5, ...]` so

``````primes = sieve [2, 3, 4, 5, 6, ...]
``````

Inline `sieve` once:

``````primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]
``````

First, `x` gets value `3` which passes the `mod 2` filter

``````primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])
``````

Inline `sieve` again (I renamed `x` to `y` to prevent confusions)

``````primes = 2 : 3 : sieve [y | y <- [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0],
y `mod` 3 /= 0]
``````

Now `x = 4` fails the `mod 2` filter but `x = 5` passes it. So

``````primes = 2 : 3 : sieve [y | y <- 5 : [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0],
y `mod` 3 /= 0]
``````

This `y = 5` also passes the `mod 3` filter so now we have

``````primes = 2 : 3 : sieve (5 : [y | y <- [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0],
y `mod` 3 /= 0])
``````

Expanding `sieve` one more time (`z` instead of `y`) gets us to

``````primes = 2 : 3 : 5 : sieve [z | z <- [y | y <- [x | x <- [6, 7, 8, ...],
x `mod` 2 /= 0],
y `mod` 3 /= 0],
z `mod` 5 /= 0]
``````

And the expansion continues on the same way.

Thursday, October 21, 2021

62
``````    #include <stdio.h>
#include <math.h>

int main(){
int num, sr, num2;
int isPrime = 1; // this is a check parameter; isPrime = 0 if number is not prime.
for(num=2; num<=100; num++){
sr = (int) sqrt(num);
for(num2=2; num2 <= sr; num2++){
//num2 <== sr to stop the innner loop
if(num%num2 == 0){
//printf("=========== %d|%dn", num,num2); // uncomment this to see if a number is divisable
isPrime = 0; // this number is not prime, cos num can be divided by num2
break;
}
}
if(isPrime){
printf("Prime number is %dn", num);
isPrime = 1; // reset the check parameter
}else{
isPrime = 1; // reset the check parameter
}
}
return 0;
}
``````

This code works. Since it works, i'll let you play with it and optimize it. If you can't let us know. We'll try to help you.

I like how you used sqrt to optimize the code.

Wednesday, October 27, 2021