Python 质数 "C-数

Question

"C-number" 是一个大于1的整数 n，满足 (b^n)mod n = b 对于所有整数 b（1 < b < n）。

简单来说，我需要写一个程序，遍历大约2000个整数（从1到2000），找出满足C-number条件的数字，同时还要检查这些数字不是质数。我似乎无法正确地让循环工作。

我有一个程序可以生成非质数的列表，还有一个可以检查输入的数字是否是C-number的程序，如果是，它会返回这个数字，如果不是，就会返回假。

我想让程序检查1到2000的所有数字，而不仅仅是我输入的那个数字，并且还要和非质数的列表进行对比。

这是我的代码：

import numpy
def primesfrom2to(n):
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
for i in xrange(1,int(n**0.5)/3+1):
    if sieve[i]:
        k=3*i+1|1
        sieve[       k*k/3     ::2*k] = False
        sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

num=range(600)
mylist =primesfrom2to(600)
s = [item for item in num if item not in mylist]
a=[]
d=[]        
from math import *
def numc(n):
    for a in range(1,n):

            c= a**n
        d=c%n       
    if a == d:
        return n
    else:
        return False
print numc(561)

Answer 1

首先，不太确定numc()是否能达到你想要的效果——根据目前的写法，那个if语句只会对范围内最后一个a的值进行测试。因为if语句不在for循环的块里，所以循环会遍历所有的赋值，而if语句只会针对最后一次迭代中赋的值进行判断。看起来你更想要的是这样的：

def numc(n):
    for a in range(1,n):
        c= a**n
        d=c%n       
        if a != d:
           return False
    return n

在这里，如果某个a的值没有通过if测试，函数就会返回False。如果所有的a值都通过了，就返回True。

其次，我的草稿和你的代码都不会返回一个数组，只会返回一个整数或布尔值。如果想要得到通过测试的值的数组，你需要对每个候选项调用这个函数。

这样你就能得到候选数组中每个成员的输出，可能是整数或者布尔值：

c_values = [numc(i) for i in range(1, 2000)]

你可以通过在循环中进行测试来获取仅通过的值：

    c_values = [numc(i) for i in range(1, 2000) if numc(i)]

你可以通过嵌套列表推导式来避免调用numc()两次：

    c_values = [i for i in [numc(j) for j in range(1, 2000)] if i]

这样首先生成完整的输出值数组，然后只返回那些为True的值。

编辑：你似乎对代码块的缩进有些困惑，或者对两个返回语句感到不解。这里有另一种方法，只用一个返回：

def numc(n):
    retval = n
    for a in range(1,n):
        c= a**n
        d=c%n       
        if a != d:
           retval = False # reset return value
           break   # halt the loop
    return retval

在这里，默认的返回值是<< n >>，如果某个<< a >>的值违反了cnumber的条件，就会在<< for >>循环中重置。在这种情况下，<< break >>会停止循环（不过这里其实不需要）。函数会返回当到达return语句时，<< retval >>的值。

我最初的草稿也有同样的效果，但那里for循环是被<< return False >>语句中断的——这也中断了函数，导致它无法到达<< return n >>。如果没有到达那个语句，也就是说没有任何<< a >>违反条件，函数就会到达并执行<< return n >>。如果一个函数有两个返回语句，它只会执行第一个到达的语句，后面的代码将被忽略。

Answer 2

最简单而且更重要的是：最干净的方法就是创建两个列表，一个用来存放你找到的质数，另一个用来存放c数字。然后遍历这两个列表，检查哪些数字在c数字中但不在质数中。另外，把质数和c数字的功能分成两个不同的函数。可以这样做：

prime_numbers = []
c_numbers = []

amount = 2000

for i in xrange(amount):
   if is_prime(i):
      prime_numbers.append(i)

   if is_c_number(i):
      c_numbers.append(i)

for i in xrange(amount):
    if i in c_numbers and (not i in prime_numbers):
        print i

Answer 3

你可能只需要修正一下缩进（很多地方都需要修正）：

def numc(n):
for a in range(1,n):
    c= a**n
    d=c%n  

在Python中，缩进是非常重要的，代码的结构基本上是通过缩进来表示的。