[stevo93]

prime = int(raw_input())
out = ''
while prime != -1:
    countPrime = 0
    for i in range(0,prime):
        if prime == 2 or prime == 3:
            out = "is a prime"
        elif prime % 2 == 0 or prime %3 == 0 or prime ==1:
            out = "not a prime"
        else:
            out = "is a prime"
        prime -= 1
        if out == 'is a prime':
            countPrime += 1
    print countPrime
    prime = int(raw_input())

the program is meant to count the number of prime numbers that fall under the the entered number.
this only works for smaller numbers once the number is too big, it outputs the wrong count
1000 is meant to 168, but rather gives 333??
please help

[sepp2k]

You're counting every number that is not divisible by 2 or 3 as a prime. That's wrong. 25 is not divisible by 2 or 3. Of course you could "fix" that by adding 5 to the numbers you check against, but that would break for 49. And if you'd add 7, it would break for 121 and so on.

To check whether a number a number is prime, you can't just check it against a constant number of divisors. You need to check whether it's divisible by any number or at least any prime number less than or equal to the square root of the number (if there is no prime number p <= sqrt(n) that divides n, there is no number that divides n (other than 1 and n itself)).

The most common way to check whether a single number n (greater than 2) is prime, is to write a loop from 2 to sqrt(n) (inclusive) that checks for each number if it divides n. If none of them do, the number is prime.

However for cases like this where you want to find all primes in a range, using a sieve is more efficient. One sieve that's relatively easy to implement is the Sieve of Eratosthenes.

[stevo93]

thanks the sieve of Eratosthenes helps a lot

[stevo93]

sorry im just getting stuck where the specific index is set to true in python?? sorry i'm new to python syntax. and im working with the sieve of Eratosthenes

[sepp2k]

To set a specific index of a list to True, you use sieve[index] = True; (where sieve is the list). However for a sieve you should start with a set full of Trues and then set individual indices to False, not True. To create a list full of Trues, you can use sieve = [True for i in range(0, size)].

[stevo93]

so were not working with any physical values, just the indices of the array, and eventually counting the true values to know how many primes there are in that range. thanks