@xiaomeng242 求10000以内的最大质数本人答案

JimmyzZZ

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

bool check(int n);
        
int main()
{
        int j = 0;
        for (int i = 0; i <= 10000; i++) {
                j = 10000 - i;
                if (check(j) == true) {
                        cout<< j;
                        break;
                }
        }
}

bool check(int n) {
    int q = 1, w = 2, p = n;
    while(p > 0) {
        if ((p % 2) != 0) {
                        q = q * w % n;
                }
        w = w * w % n;
        p = p / 2;
    }
    if ((q - 2) % n == 0) {
                return true;
        }
        else {
                return false;
        }
}

别问我为什么来写C++了，因为Rust的生命周期快把我弄死了。。
这个算法虽然在数学上不成立，但是我认为这里投机取巧应该问题不大。虽然我代码写的稀烂
参考了快速幂取模，用了啥算法你猜.
另外我目前没办法编译并添加计时的东西，等会儿有机会加。

skystars

费马小定理？

xiaomeng242

肯定是 快速幂取模算法了

有空你把时间计算的加一下，看看谁的快

JimmyzZZ

xiaomeng242 发表于 2022-8-9 15:52
肯定是 快速幂取模算法了

有空你把时间计算的加一下，看看谁的快  ...

其实核心是费马小定理
本来想用威尔逊的算法的但是太慢了

xiaomeng242

JimmyzZZ 发表于 2022-8-9 16:15
其实核心是费马小定理
本来想用威尔逊的算法的但是太慢了

我用的是 埃拉托斯特尼筛法，用Python不到6ms就算了出来。、
如果放上修饰器的话，速度就接近于c++了
待会上代码

JimmyzZZ

xiaomeng242 发表于 2022-8-9 16:37
我用的是 埃拉托斯特尼筛法，用Python不到6ms就算了出来。、
如果放上修饰器的话，速度就接近于c++了
待 ...

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
using namespace std;

bool check(int n);

int main()
{
    string readkey = "";
    clock_t start = clock();
    int j = 0;
    for (int i = 0; i <= 10000; i++) {
        j = 10000 - i;
        if (check(j) == true) {
            cout << j << endl << "Time: " << clock() - start << "ms" << endl;
            cin >> readkey;
            break;
        }
    }
}

bool check(int n) {
    int q = 1, w = 2, p = n;
    while (p > 0) {
        if ((p % 2) != 0) {
            q = q * w % n;
        }
        w = w * w % n;
        p = p / 2;
    }
    if ((q - 2) % n == 0) {
        return true;
    }
    else {
        return false;
    }
}

我这里可能是精度不够，显示的是0ms，只能说费马小定理+快速幂取模的确不错，但是数值达到一定数量级后会出现错误
注意，CPU是3210M，内存4G DDR3，过几天换12700+16G的试试

xiaomeng242

JimmyzZZ 发表于 2022-8-9 20:28
[mw_shl_code=cpp,true]#include
#include
using namespace std;

不太可能吧……0毫秒就算了出来？

他有计算这个过程就说明他需要时间，0ms有点不正常

JimmyzZZ

xiaomeng242 发表于 2022-8-9 23:12
不太可能吧……0毫秒就算了出来？

他有计算这个过程就说明他需要时间，0ms有点不正常 ...

我也也得很奇怪，肯定是精度不够了

xiaomeng242

JimmyzZZ 发表于 2022-8-10 06:39
我也也得很奇怪，肯定是精度不够了

感觉你时间算错了，凭借直觉

不过还是很羡慕学编译性语言的大佬

xiaomeng242

JimmyzZZ 发表于 2022-8-9 20:28
[mw_shl_code=cpp,true]#include
#include
using namespace std;

太逊了，python对时间可以精确到小数点后15位的