4

我真的是python的初学者，所以我为缺乏知识而道歉，但我问的原因是阅读Python手册和教程（http://docs.python.org/2.7/tutorial）我是不能完全掌握循环是如何工作的。我写了一些简单的程序，所以我想我已经掌握了基础知识，但是无论出于何种原因，这个旨在列出所有小于或等于 n 的素数的程序都不起作用：

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"

例如，当我输入 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

这看起来几乎是正确的，但由于某种原因包含 27、35、95，它们当然是复合的。我一直在尝试区分我的循环的工作方式，但我只是看不到它突然跳过检查可分性的地方。我想如果有人看过，他们可以向我解释导致这种情况的语法是什么。非常感谢！

4

14 回答 14

17

我实际上会将程序重组为如下所示：

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 loop), and works perfectly.

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

The inner one iterates to all numbers from 2 to p. If it reaches a number that divides evenly into p, then it breaks out of the inner loop.

The else block executes every time the for loop isn't broken out of (printing the prime numbers).

Then the program prints 'Done' after it finishes.

As a side note, you only need to iterate through 2 to the square root of p, since each factor has a pair. If you don't get a match there won't be any other factors after the square root, and the number will be prime.

于 2013-02-01T23:23:12.107 回答
6

Your code has two loops, one inside another. It should help you figure out the code if you replace the inner loop with a function. Then make sure the function is correct and can stand on its own (separate from the outer loop).

Here is my rewrite of your original code. This rewrite works perfectly.

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() doesn't touch the loop index of the outer loop. It is a stand-alone pure function. Incrementing p inside the inner loop was the problem, and this decomposed version doesn't have the problem.

Now we can easily rewrite using for loops and I think the code gets 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 in. So the inner loop, which checks for < n, we can simply call range(2, n) but for the outer loop, where we want <= n, we need to add one to n so that n will be included: range(2, n+1)

Python has some built-in stuff that is fun. You don't need to learn all these tricks right away, but here is another way you can write is_prime():

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

This works just like the for loop version of is_prime(). It sets i to values from range(2, n) and checks each one, and if a test ever fails it stops checking and returns. If it checks n against every number in the range and not any of them divide n evenly, then the number is prime.

Again, you don't need to learn all these tricks right away, but I think they are kind of fun when you do learn them.

于 2013-02-01T23:45:42.150 回答
2

This should work and is bit more 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)
于 2016-01-18T20:33:54.680 回答
1

i找到非素数后不要重新启动循环

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"

循环执行while主体，然后检查顶部的条件是否为True，如果为真，则再次执行主体。for循环为迭代器中的每个项目执行一次主体。

于 2013-02-01T23:00:52.377 回答
1

请将您的代码段与下面粘贴的代码段进行比较，您会发现哪里错了。

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
于 2013-02-01T23:17:19.920 回答
0 
for i in range(2, p):
    if p%i == 0:
        p=p+1 
     print "%s" % p,
     p=p+1

I am going to tell your error only,in line 3 you are incrimenting p but actually what you are missing is your i if your i in previous case is let say 13 then it will check your loop after 13 but it is leaving 2,3,5,7,11 so its an error .that is what happening in case of 27 your i before 27 is 13 and now it will check from 14.and I don't think u need an solution.

于 2014-08-05T08:27:27.513 回答
0 
def is_prime(n):
    if n>=2:
        for i in range(2, n):
            if n%i == 0:
                return False
        return True
    else:
        return False

To find PRIME NUMBER

于 2017-02-18T07:29:02.890 回答
0

Let's do a couple more improvements.

  1. You know 2 is the only even prime number, so you add 2 in your list and start from 3 incrementing your number to be checked by 2.
  2. Once you are past the half-way point (see above sqrt and * examples), you don't need to test for a prime number.
  3. If you use a list to keep track of the prime numbers, all you need to do is to divide by those prime numbers.

I wrote my code and each of the above items would improve my code execution time 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
于 2017-05-19T23:27:01.787 回答
0

This in my opinion is a more optimised way. This finds all the prime numbers up to 1,000,000 in less than 8 seconds on my setup.

It is also one of my very first attempts at python, so I stand to be corrected

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()
于 2017-07-24T12:18:11.577 回答
0 
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')
于 2017-08-09T20:06:50.757 回答
0 
def findprime(num):
  count = 0
  for i in range(1,num+1):
    list1 = []
    for ch in range(1,i+1):
      if i%1==0 and i%ch==0:
        list1.append(ch)
    if len(list1)==2:
      count += 1
      print(i,end=", ")
  print()
  return count  
num2 = int(input("enter a number: "))
result=findprime(num2)
print("prime numbers between 1 and",num2,"are",result)
于 2018-04-25T17:21:22.297 回答
0

Here's a more extensive example with optimization in mind for Python 3.

import sys

inner_loop_iterations: int = 0

def is_prime(n):
    a: int = 2
    global inner_loop_iterations

    if n == 1:
        return("Not prime")
    elif n == 2:
        return("Prime")

    while a * a <= n + 1:
        inner_loop_iterations += 1
        # This if statement reduces the number of inner loop iterations by roughy 50%
        # just weeding out the even numbers.
        if a % 2 == 0:
            a += 1
        else:
            a += 2

        if n % 2 == 0 or n % a == 0:
            return ("Not prime")
    else:
        return ("Prime")

while True:
    sys.stdout.write("Enter number to see if it's prime ('q' to quit): ")
    n = input()
    if not n:
        continue
    if n == 'q':
        break

    try:
        n = int(n)
    except ValueError:
        print("Please enter a valid number")

    if n < 1:
        print("Please enter a valid number")
        continue

    sys.stdout.write("{}\n".format(is_prime(n)))
    sys.stderr.write("Inner loops: {}\n\n".format(inner_loop_iterations))
    inner_loop_iterations=0

This program has two main optimizations, first it only iterates from 2 to the square root of n and it only iterates through odd numbers. Using these optimizations I was able to find out that the number 1000000007 is prime in only 15811 loop iterations.

于 2018-09-27T22:54:30.440 回答
0

My fast implementation returning the first 25 primes:

#!/usr/bin/env python3

from math import sqrt

def _is_prime(_num: int = None):
    if _num < 2:
        return False
    if _num > 3 and not (_num % 2 and _num % 3):
        return False
    return not any(_num % _ == 0 for _ in range(3, int(sqrt(_num) + 1), 2))

_cnt = 0
for _ in range(1, 1000):
        if _is_prime(_):
        _cnt += 1
        print(f"Prime N°: {_:,} | Count: {_cnt:,}")
于 2021-04-21T06:19:24.980 回答
-1

Better use 

for i in range(2, p//2 + 1):
于 2013-02-01T23:35:58.433 回答