python algorithm for prime numbers

Question

Assume the availability of a function is_prime . Assume a variable n has been associated with positive integer. Write the statements needed to find out how many prime numbers (starting with 2 and going in increasing order with successively higher primes [2,3,5,7,11,13,...]) can be added before exceeding n . Associate this number with the variable k .

 def main():
    n=int(input('n: '))
    k=0
    i=2
    sum=0

    while sum<=n:
        if is_prime(i):
            sum+=i
            i+=1
            k+=1
        print(k)



def is_prime(n):

    for divisor in range(2,int(n**0.5)+1):
        if n/divisor==int(n/divisor):
            return False
    return True

main()

would really appreciate some pointers.

I modified the code a little bit and it is working fine but the program that grades these codes says that I almost certainly should be using a + sign some where. I have no idea. Modified code is:

while sum<=n:

        if is_prime(i):

            sum+=i
            k+=1
            i+=1
    print(k)

output:

n: 10

i: 2

2

i: 3

5

when it should actually go upto i=5 and total =10.

this program is not working? I don't know how to modify it to make it work. — , Feb 06 '14 at 05:46
"Not working" is about the most detailed error description you can get on stackoverflow. — Hyperboreus, Feb 06 '14 at 05:47
You need to describe what isn't working. What's the output of your program? — jayelm, Feb 06 '14 at 05:49
n: 10 3 4 this is my output and the loop is just going on and on. — , Feb 06 '14 at 05:53
As soon as `i` is not prime, you never increment `i` again... — Hyperboreus, Feb 06 '14 at 06:05
first of all do you want know what prime number is ? if you know that do you ever try to understand why you are going upto the square root of the number, if yes you should be able to fix this line ` if n/divisor==int(n/divisor):` — James Sapam, Feb 06 '14 at 06:27
I know that my is_prime function is working fine. I don't think I need to do anything with that. — , Feb 06 '14 at 06:42

score 2 · Answer 1 · edited May 23 '17 at 12:21

2

There is actually more efficient why to solve this problem, it is Sieve of Eratosthenes. The basic idea is to generate array of numbers from 2 till n. Then you iterate over this array starting from 2 and replace all numbers, which mod by i == 0 with -1 or delete them.

If you are getting stuck you can check implementation here.

Sieve of Eratosthenes - Finding Primes Python

edited May 23 '17 at 12:21

Community

1
1

answered Feb 06 '14 at 06:42

Slow Harry

1,857
3
24
42

We haven't done array yet. Hence, I am using this way. I understand that it is based on Sieve of Eratosthenes idea and that comes from abstract algebra. I have checked my is_prime function and it seems to be working fine. It's the while loop that is giving me the trouble. – Feb 06 '14 at 06:49
@cobra may be this link will be helpful :) – Slow Harry Feb 06 '14 at 06:53

score 0 · Answer 2 · answered Feb 06 '14 at 06:36

0

What you certainly ought to be using is the space character around operators. Also, your alignment is wacky. In Python, alignment indicates structure, and your rewrite will make any interpreter complain (at least, at it's displayed here). If a program (or a robotic TA) is reading and grading your work, and it thinks you need a + sign somewhere, then perhaps it wants to see "sum = sum + i" somewhere. I'll use that. So try this:

def main():
    n = int(input('n: '))
    k = 0
    i = 2
    sum = 0

    while sum <= n:
        if is_prime(i):
            sum = sum + i  # nothing wrong with "sum += i"
            k += 1
        i += 1    # put this inside "if" ==> loop forever 
    print(k)

def is_prime(m):
    for divisor in range(2, int(m**0.5) + 1):
        if m % divisor == 0:
            return False
    return True

main()

answered Feb 06 '14 at 06:36

BrianO

1,496
9
12

Now, it says that I am using an incorrect number somewhere. Go figure. – Feb 06 '14 at 06:40
Maybe it means 0.5. Try being simple-minded: change the loop in `is_prime` to: for divisor in range(2, n-1): # same as before You'll want to add a check in `main` that `n >= 2` :) If it isn't, print `0` then `return`. – BrianO Feb 06 '14 at 06:43
Oops, can't edit my comment above anymore. If I could, it'd read: change the loop in `is_prime` to: `for divisor in range(2, n-1): # same loop body as before` – BrianO Feb 06 '14 at 06:51

Sergii Khaperskov · Accepted Answer · 2014-02-06T07:36:44.260

-1

if n/divisor==int(n/divisor):

This is wrong. When you divide 2 integers you get integer as a result. So 5/2 = 2. Replace it with

if n%divisor == 0:

EDITED: your modified loop looks almost correct. If I understand your task right it should be

while sum<=n:
    if is_prime(i):
        sum+=i
        k+=1
    i+=1
print(k)

EDITED2: probably you want to stop as soon as sum + next prime is bigger then n and not add another prime value.

while True:
    if is_prime(i):
        if(sum + i > n)
            break;
        else:
            sum += i
            k += 1
    i += 1 
print(k)

edited Feb 06 '14 at 07:36

answered Feb 06 '14 at 05:52

Sergii Khaperskov

451
2
6

This depends on the python version and we don't even know which one OP uses. But I guess python3 (because of `int(input())`) and there `5/2 = 2.5`. – Hyperboreus Feb 06 '14 at 06:02
Oh, I do not know how it works in python 3. Anyway interpreter dependent implementation is not a way to go. Verifying if division remainder is zero looks more clear and works with any interpreter. – Sergii Khaperskov Feb 06 '14 at 06:09
1

This has nothing to do with "interpreter dependence". It is differences between the specs of py2 and py3. Like `ínput` and `raw_input`. Btw OP's problem is in his `while` loop. – Hyperboreus Feb 06 '14 at 06:11
Yup, I am almost certain, the problem is in the while loop. Any idea about how to modify it? – Feb 06 '14 at 06:21

python algorithm for prime numbers

3 Answers3