相关疑难解决方法(0)

请问有人请告诉我这段代码我做错了什么？无论如何,它只是打印'计数'.我只想要一个非常简单的素数发生器(没什么特别的).

import math

def main():
    count = 3
    one = 1
    while one == 1:
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                continue
            if count % x != 0:
                print count

        count += 1

是否有一个函数可以返回第n个素数的近似值？我认为这将类似于近似反向素数计数功能.例如,如果我给这个函数25它将返回一个大约100的数字,或者如果我给这个函数1000它将返回一个大约8000的数字.我不在乎返回的数字是否是素数,但我确实想要它要快(所以不产生前n个素数以返回第n个.)

我想这样我可以使用筛子(Eratosthenes或Atkin)生成前n个素数.因此,理想情况下,n th 的近似值永远不会低估实际第n个素数的值.

(更新:请参阅我的答案,找到找到第n个素数上限的好方法.)

多年来,我一直对寻找更好的素数识别器的问题感兴趣.我意识到这是一个巨大的学术研究和学习领域 - 我对此感兴趣只是为了好玩.这是我在C(下面)中首次尝试可能的解决方案.

我的问题是,你能否提出一个改进(没有引用网上的其他参考,我正在寻找实际的C代码)？我想从中获得的是更好地理解确定这样的解决方案的性能复杂性.

我是否正确地得出结论,这个解决方案的复杂性是O(n ^ 2)？

#include <stdio.h>
#include <math.h>

/* isprime                                                           */
/* Test if each number in the list from stdin is prime.              */
/* Output will only print the prime numbers in the list.             */

int main(int argc, char* argv[]) {

    int returnValue = 0;
    int i;
    int ceiling;
    int input = 0;
    int factorFound = 0;

    while (scanf("%d", &input) != EOF) {

        ceiling = (int)sqrt(input);
        if (input == 1) {
            factorFound = 1;
        }

        for …