Python Beginner Loop (prime search)

Question

I'm really a python beginner, so I apologize for the lack of knowledge, but the reason I ask is to read the Python manual and tutorial ( http://docs.python.org/2.7/tutorial ) I can't fully understand how cycles work. I wrote some simple programs, so I think I'm getting the basics, but for some reason this program, designed to list all primes less than or equal to n, does not work:

n = int(raw_input("What number should I go up to? ")) p = 2 while p <= n: for i in range(2, p): if p%i == 0: p=p+1 print "%s" % p, p=p+1 print "Done" 

Exit when I enter, for example, 100:

 2 3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87 89 95 97 101 Done 

Which looks almost right, but for some reason contains 27, 35, 95, which are, of course, complicated. I'm trying to make out how my loop works, but I just can't see where it unexpectedly checks for divisibility. I thought that if someone looked, they could explain to me how about the syntax. Thanks a bunch!

Answer 1

I would actually restructure the program so that it looks 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 ) and works fine.

The outer for loop iterates over all numbers from 2 to n .

Internal is repeated with all numbers from 2 to p . If it reaches a number that evenly divides by p , it breaks out of the inner loop.

The else block is executed every time the for loop is not interrupted (printing prime numbers).

The program then prints 'Done' after completion.

As a side note, you only need to thin through the 2 square root of p , since each factor has a pair. If you do not get a match, there will be no other factors after the square root, and the number will be prime.

Answer 2

There are two loops in the code, one inside the other. This will help you understand the code if you replace the inner loop with a function. Then make sure that the function is correct and can stand by itself (separately from the external circuit).

Here is my rewriting source code. This rewriting works great.

 def is_prime(n): i = 2 while i < n: if n%i == 0: return False i += 1 return True n = int(raw_input("What number should I go up to? ")) p = 2 while p <= n: if is_prime(p): print p, p=p+1 print "Done" 

Note that is_prime() does not apply to the loop index of the outer loop. This is a standalone net function. The problem of adding p inside the inner loop was a problem, and this decomposed version has no problem.

Now we can easily rewrite it with for loops, and I think the code will be improved:

 def is_prime(n): for i in range(2, n): if n%i == 0: return False return True n = int(raw_input("What number should I go up to? ")) for p in range(2, n+1): if is_prime(p): print p, print "Done" 

Note that in Python, range() never includes the upper bound that you pass into. So the inner loop that checks for < n can just be called range(2, n) , but for the outer loop where we want <= n , we need to add it to n to include n : range(2, n+1)

Python has built-in stuff that is fun. You do not need to learn all these tricks right away, but here you can write is_prime() :

 def is_prime(n): return not any(n%i == 0 for i in range(2, n)) 

This works the same as the for is_prime() loop version. It sets i values ​​from range(2, n) and checks each, and if the test ever fails, it stops checking and returns. If he checks n for every number in the range, and none of them evenly divide n , then the number is prime.

Again, you don’t need to learn all these tricks right away, but I think they are very funny when you learn them.

Answer 3

you do not restart cycle i after you find a non-line

 p = i = 2 while p <= n: i = 2 while i < p: if p%i == 0: p += 1 i = 1 i += 1 print p, p += 1 print "Done" 

A while loop executes the body, and then checks if the condition is at the top of True , if true, it executes the body again. A for loop executes the body once for each element in the iterator.

Answer 4

Please compare your snippet with the one inserted below and you will notice where you were wrong.

 n = int(raw_input("What number should I go up to? ")) p = 2 while p <= n: is_prime=True for i in range(2, p): if p%i == 0: is_prime=False break; if is_prime==True: print "%d is a Prime Number\n" % p p=p+1 

Answer 5

This should work and is a bit optimized.

 import math for i in range(2, 99): is_prime = True for j in range(2, int(math.sqrt(i)+1)): if i % j == 0: is_prime = False if is_prime: print(i) 

Answer 6

 for i in range(2, p): if p%i == 0: p=p+1 print "%s" % p, p=p+1 

I'm going to tell only your mistake, on line 3 you include p, but in fact, what you are missing is your i, if your self in the previous case can say 13, then it will check your loop after 13, but it 2,3,5,7,11 will go away, so this is a mistake. This is what happens in the case of your 27, I to 27, is 13, and now it will check with 14. and I do not think you need a solution.

Answer 7

 def is_prime(n): if n>=2: for i in range(2, n): if n%i == 0: return False return True else: return False 

Find PRIME NUMBER

Answer 8

Make a couple more improvements.

• You know that 2 is the only even prime, so you add 2 to your list and start with 3, increasing the number you need to check by 2.
• As soon as you go half way (see sqrt and * examples), you do not need to check a simple number.
• If you use a list to track primes, all you have to do is separate these primes.

I wrote my code, and each of the above elements will improve the execution time of my code by about 500%.

 prime_list=[2] def is_prime(a_num): for i in prime_list: div, rem = divmod(a_num, i) if rem == 0: return False elif div < i: break; prime_list.append(a_num) return True 

Answer 9

 print('Enter a Number: ') number=abs(int(input())) my_List=[0,1] def is_prime(n): if n in my_List: return True elif n>=2: for i in range(2, n): if n%i == 0: return False return True else: return False if is_prime(number): print("%d is Prime!"%number) else: print(number,'is not prime') 

Answer 10

Better to use

 for i in range(2, p//2 + 1): 

Answer 11

This, in my opinion, is a more optimized way. It finds all primes up to 1,000,000 in less than 8 seconds on my setup.

This is also one of my first attempts in python, so I have to fix it

 class prime: def finder (self): import math n = long(raw_input("What number should I go up to? ")) for i in range(2, n): is_prime = True if i % 2 == 0: is_prime = False for j in range(3, long(math.sqrt(i) + 1), 2): if i % j == 0: is_prime = False break if is_prime: print(i) prime().finder()