Counting primes

Question

I am new to programming and I found a problem on the internet to show the 1000th prime number. But the problem is that my code but I have some problems with it.

count=0
prime=[]
n=2

while count != 1000:
    if n == 2 or n == 3 or n == 5 or n == 7 or n == 11:
        prime.append(n)
        n=n+1
        count=count+1
    elif n%2 == 0 or n%3 == 0 or n%5 == 0 or n%7 == 0 or n%11 == 0:
        n=n+1
    else:
        prime.append(n)
        n=n+1
        count=count+1

print(prime[999])

The problem comes when I have a number like 403. According to the code I wrote it is prime but actually it is not because it can be divided by 13 and 31.

I came up a solution but I don't know how to do it and if there is a better solution. If you help me, please try preserve my code, please don't give me entirely new code.

My solutions is:

elif n%prime[:]==0
     n=n+1

So basically what I'm trying to do is trying to divide the number 403, for example, to any of the other prime numbers that I've recorded earlier. But for some reason this code gives me an error. I want to tell the program "devide n to EVERY number in the list". Thanks for the help :)

What is `%prime[:]==0` supposed to do? Do you mean `for i in prime: if n % i==0`? — Padraic Cunningham, Apr 14 '16 at 09:20

score 0 · Accepted Answer · answered Apr 14 '16 at 09:25

You can use "any".

In [15]: prime = [2, 3, 5, 7, 11]

In [16]: n = 15

In [17]: any(n%p == 0 for p in prime)
Out[17]: True

In [18]: n = 17

In [19]: any(n%p == 0 for p in prime)
Out[19]: False

In [20]: n = 19

In [21]: any(n%p == 0 for p in prime)
Out[21]: False

Basically, it will tell you if given number is divisible by "any" of the number in the list.

score 0 · Answer 2 · answered Apr 14 '16 at 09:29

there are several algorithm to count prime numbers, what you need first is first how to decide whether a function isPrime(n) will return true or false and if you need that this funciton isPrime(n) should be under o(n). There are several approach to do this, here are the possibilities:

def isPrime(n):
    i = 2;

    while i*i < n:
        if n % i == 0:
            return false
        i = i + 1
    return true;

this one will give you prime or not with complexity o(n^1/2), should be sufficient for you, after this the next thing you need to do is:

counter = 0
number = 2
while counter < 1000:
    if isPrime(number):
        counter = counter + 1;
    number = number + 1
print number;

i havent tried this code yet but the concept should be there

Counting primes

2 Answers2