c - C语言的Euler 7项目

Question

我知道在不同的论坛上也有很多关于此的主题，但我的问题是：

Q 1. 对于欧拉问题 7（寻找第 10001 个素数），这是我自己想到的代码。

#include <stdio.h>
int main()
{
    int i,j,k=0,m=0,num;
    for(i=1;m<10001;i++)
    {
        k=0;
        for(j=2;j<i;j++)
        {
            if(i%j!=0)
                k++;
        }
        if(k+2==i)
        {    
            m++;
            num=i;
        }  
    }
    printf("%d %d",num,m);
}

这个问题应该显示第 10000 个素数（m<10001），但它显示第 10001 个素数，这是为什么呢？

Answer 1

循环在 10001 时中断，m这是它打印 10001 的原因m。由于m从 开始0，它打印第 10001 个素数。在您的代码中，循环从0...10000（10001 次）开始运行。

将条件更改为m<10000即循环从0...9999(10000 次) 开始运行，并且m在循环结束时将具有10000.

Answer 2

尝试实现埃拉托色尼筛法，因为它会跳过检查所有素数的倍数。

Answer 3

这是我的优化代码：

#include<iostream>
using namespace std;

bool prime(int n){ 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 

    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 

    return true; 
}

int main()
{
    int arr[100000],j=0; 

    for(int i=0;i<1000000;i++){
        if(prime(i))
            arr[j++]=i;
    }
    cout << arr[99999] << endl;
}

我试图尽可能地降低时间复杂度。

我的解决方案的算法：

1) 我使用了这样一个事实，即每个质数都是 6N-1 或 6N+1 的形式，其中 N 是自然数。

2）检查数字是否为素数，检查直到 sqrt(number) 的因子就足够了，因为它会降低代码的时间复杂度。

3）我没有使用 Eratosthenes 算法的筛子，因为我们没有范围直到我们必须运行循环。