# prime number counter problem

Page 1 of 1

## 5 Replies - 780 Views - Last Post: 19 April 2012 - 10:41 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=275872&amp;s=87a005137a483c8481d08ffe949e9c71&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 stevo93

Reputation: 0
• Posts: 10
• Joined: 09-April 12

# prime number counter problem

Posted 19 April 2012 - 05:33 AM

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

Is This A Good Question/Topic? 0

## Replies To: prime number counter problem

### #2 sepp2k

• D.I.C Lover

Reputation: 1690
• Posts: 2,553
• Joined: 21-June 11

## Re: prime number counter problem

Posted 19 April 2012 - 06:35 AM

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.

### #3 stevo93

Reputation: 0
• Posts: 10
• Joined: 09-April 12

## Re: prime number counter problem

Posted 19 April 2012 - 09:20 AM

thanks the sieve of Eratosthenes helps a lot

### #4 stevo93

Reputation: 0
• Posts: 10
• Joined: 09-April 12

## Re: prime number counter problem

Posted 19 April 2012 - 10:22 AM

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

### #5 sepp2k

• D.I.C Lover

Reputation: 1690
• Posts: 2,553
• Joined: 21-June 11

## Re: prime number counter problem

Posted 19 April 2012 - 10:31 AM

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)].

### #6 stevo93

Reputation: 0
• Posts: 10
• Joined: 09-April 12

## Re: prime number counter problem

Posted 19 April 2012 - 10:41 AM

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