求素数和求原根

用C++写一个高效求原根的程序，要求：输入一个数字，输出该数字的所有原根到d盘的"yuangen.txt"文件，并给出详细注释。

下面是一个用C++编写的程序，用于计算给定数字的所有原根，并将结果输出到 D 盘的 "yuangen.txt" 文件中。程序中包含了详细的注释。

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

// 函数声明
bool isPrime(int n);
int gcd(int a, int b);
int power(int base, int exp, int mod);
bool isPrimitiveRoot(int g, int p, vector<int>& factors);

// 主函数
int main() {
    int p;
    cout << "请输入一个素数：";
    cin >> p;

    if (!isPrime(p)) {
        cout << p << " 不是一个素数！" << endl;
        return 1;
    }

    // 找到 p-1 的所有质因数
    int phi = p - 1;
    vector<int> factors;
    for (int i = 2; i <= sqrt(phi); i++) {
        while (phi % i == 0) {
            if (find(factors.begin(), factors.end(), i) == factors.end()) {
                factors.push_back(i);
            }
            phi /= i;
        }
    }
    if (phi > 1) {
        factors.push_back(phi);
    }

    // 找出所有原根
    vector<int> primitiveRoots;
    for (int g = 2; g < p; g++) {
        if (isPrimitiveRoot(g, p, factors)) {
            primitiveRoots.push_back(g);
        }
    }

    // 将结果写入文件
    ofstream outFile("D:\\yuangen.txt");
    if (outFile.is_open()) {
        outFile << "原根为：\n";
        for (int root : primitiveRoots) {
            outFile << root << endl;
        }
        outFile.close();
        cout << "原根已写入 D:\\yuangen.txt 文件。" << endl;
    } else {
        cout << "无法打开文件！" << endl;
    }

    return 0;
}

// 检查是否为素数
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 快速幂计算
int power(int base, int exp, int mod) {
    int result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1; // 右移一位，相当于整除2
        base = (base * base) % mod;
    }
    return result;
}

// 检查 g 是否为原根
bool isPrimitiveRoot(int g, int p, vector<int>& factors) {
    for (int factor : factors) {
        int exponent = (p - 1) / factor;
        if (power(g, exponent, p) == 1) {
            return false;
        }
    }
    return true;
}

以上程序可以有效地计算给定素数的所有原根，并将结果保存到指定文件中。程序中的函数分别负责检查素数、计算最大公约数、执行快速幂运算以及检查原根条件。

用C++写一个高效求质数的程序，要求：输入一个数字，输出该数字以内所有质数到d盘的"sushu.txt"文件，并给出详细注释。

下面是一个用C++编写的程序，用于计算给定数字以内的所有质数，并将结果输出到 D 盘的 "sushu.txt" 文件中。程序中包含了详细的注释。

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

// 函数声明
bool isPrime(int n);
void findPrimes(int limit, vector<int>& primes);

int main() {
    int n;
    cout << "请输入一个正整数：";
    cin >> n;

    if (n < 2) {
        cout << "请输入大于等于2的整数！" << endl;
        return 1;
    }

    // 存储质数的向量
    vector<int> primes;
    findPrimes(n, primes);

    // 将结果写入文件
    ofstream outFile("D:\\sushu.txt");
    if (outFile.is_open()) {
        outFile << "小于或等于 " << n << " 的质数有：\n";
        for (int prime : primes) {
            outFile << prime << endl;
        }
        outFile.close();
        cout << "质数已写入 D:\\sushu.txt 文件。" << endl;
    } else {
        cout << "无法打开文件！" << endl;
    }

    return 0;
}

// 判断一个数是否为质数
bool isPrime(int n) {
    if (n <= 1) return false; // 1 及以下不是质数
    if (n <= 3) return true;  // 2 和 3 是质数
    if (n % 2 == 0 || n % 3 == 0) return false; // 剔除 2 和 3 的倍数

    // 检查从 5 开始的质数，使用 6k ± 1 方法
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

// 查找小于等于 limit 的所有质数
void findPrimes(int limit, vector<int>& primes) {
    for (int i = 2; i <= limit; ++i) {
        if (isPrime(i)) {
            primes.push_back(i); // 将质数添加到向量中
        }
    }
}

程序详细说明：

1. isPrime 函数：

   • 用于判断一个整数是否为质数。
   • 处理小于等于 1 的情况，直接返回 false。
   • 对于小于等于 3 的数，返回 true 的情况。
   • 剔除所有偶数和 3 的倍数。
   • 使用 6k±1 方法来检查更大的数，其中 k 为正整数。

2. findPrimes 函数：

   • 用于查找小于等于给定限制的所有质数。
   • 将找到的质数存入一个向量中。

3. 文件输出：

   • 程序将找到的质数写入 D 盘的 "sushu.txt" 文件中。

4. 输入检查：

   • 程序确保用户输入的数字大于等于 2。

5. 控制台输出：

   • 程序会在控制台显示文件写入成功的提示。