相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

我在一个编程网站上遇到了以下这个问题:彼得希望为他的密码系统生成一些素数.帮助他!你的任务是生成两个给定数字之间的所有素数!

输入

输入以单行中的测试用例数t开始(t <= 10).在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n <= 1000000000,nm <= 100000).

我提出了以下解决方案:

import java.util.*;

public class PRIME1 {
    static int numCases;
    static int left, right;
    static boolean[] initSieve = new boolean[32000];
    static boolean[] answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        numCases = sc.nextInt();
        initSieve[0] = true;
        initSieve[1] = true;
        Sieve();
        for (int j = 0; j < numCases; j++) {
            String line = sc.next();
            String line2 = sc.next();
            left = Integer.parseInt(line);
            right = …

我用C语言编写了该程序，用于测试数字是否为质数。我还不了解算法的复杂性以及所有有关Big O的知识，因此我不确定将迭代和递归相结合的方法是否比使用纯迭代方法更有效。

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

typedef struct primenode{
    long int key;
    struct primenode * next;
}primenode;

typedef struct{
    primenode * head;
    primenode * tail;
    primenode * curr;
    unsigned long int size;
}primelist;

int isPrime(long int number, primelist * list ,long int * calls, long int * searchcalls);
primenode * primelist_insert(long int prime, primelist * list);
int primelist_search(long int searchval, primenode * searchat, long int * calls);
void primelist_destroy(primenode * destroyat);

int main(){
    long int …

如何编写一个程序来查找给定数字后的n个素数？例如,在100之后的前10个素数,或在1000之后的前25个素数.编辑:下面是我尝试的.我正在以这种方式获得输出,但是我们可以在不使用任何素性测试函数的情况下进行输出吗？

#include<stdio.h>
#include<conio.h>
int isprime(int);
main()
{
    int count=0,i;
    for(i=100;1<2;i++)
    {
        if(isprime(i))
        {
            printf("%d\n",i);
            count++;
            if(count==5)
                break;
        }
    }
    getch();
}
int isprime(int i)
{
    int c=0,n;
    for(n=1;n<=i/2;n++)
    {
        if(i%n==0)
        c++;
    }
    if(c==1)
        return 1;
    else
        return 0;
}