Asked  7 Months ago    Answers:  5   Viewed   25 times

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

 Answers

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
 
penpen
answered 7 Months ago
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
 
Seankala
answered 4 Months ago
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
 
Grzegorz
answered 2 Months ago
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
 
rorymorris
answered 1 Month ago
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
 
lauda
answered 1 Month ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share