引言
在數字世界中，素數被視為一種奧秘的存在。它們存在獨特的性質，使得它們在密碼學、收集保險等範疇扮演着重要角色。C言語作為一種高效的編程言語，為處理大年夜數素數打算供給了富強的支撐。本文將揭秘C言語大年夜數素數打算技能，幫助讀者輕鬆控制數字世界中的奧秘力量。
素數的基本不雅點
素數是指在大年夜於1的天然數中，除了1跟它本身外，不克不及被其他天然數整除的數。比方，2、3、5、7、11等都是素數。素數在數學、打算機科學等範疇有着廣泛的利用。
C言語大年夜數素數打算方法
1. 蠻力法
蠻力法是一種簡單直不雅的素數斷定方法。它經由過程逐一實驗從2到待測數字的平方根（包含平方根）對該數字停止取模。假如任何取模操縱的成果為0，則該數字不是素數；不然，該數字是素數。
以下是一個利用C言語實現的蠻力法斷定素數函數的示例：
#include <stdio.h>
#include <math.h>
int isprime(int num) {
if (num < 2) return 0;
if (num == 2) return 1;
if (num % 2 == 0) return 0;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return 0;
}
return 1;
}
int main() {
int num;
printf("請輸入一個正整數：");
scanf("%d", &num);
if (isprime(num)) {
printf("%d是素數\n", num);
} else {
printf("%d不是素數\n", num);
}
return 0;
}
2. 埃拉托斯特尼篩法
埃拉托斯特尼篩法是一種更高效的素數斷定方法。它經由過程創建一個標記數組來跟蹤從2到給定範疇內的每個數字能否為素數。這種方法增加了斷定複雜度，實用於尋覓一定範疇內的全部素數。
以下是一個利用C言語實現的埃拉托斯特尼篩法尋覓小於等於n的全部素數的示例：
#include <stdio.h>
#include <string.h>
void sieveof_eratosthenes(int n) {
int is_prime[n + 1];
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = 0;
is_prime[1] = 0;
for (int p = 2; p * p <= n; p++) {
if (is_prime[p]) {
for (int i = p * p; i <= n; i += p) {
is_prime[i] = 0;
}
}
}
for (int p = 2; p <= n; p++) {
if (is_prime[p]) {
printf("%d ", p);
}
}
printf("\n");
}
int main() {
int n;
printf("請輸入一個正整數：");
scanf("%d", &n);
sieveof_eratosthenes(n);
return 0;
}
3. Rabin-Miller生性測試
Rabin-Miller生性測試是一種基於概率的素數斷定方法。它經由過程抉擇一個隨機的整數a（1 以下是一個利用C言語實現的Rabin-Miller生性測試的示例： 經由過程以上介紹，讀者可能懂掉掉落C言語大年夜數素數打算的基本方法。在現實利用中，可能根據具體須要抉擇合適的算法，以進步打算效力。盼望本文能幫助讀者輕鬆控制數字世界中的奧秘力量。#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long long modular_pow(long long base, long long exponent, long long modulus) {
long long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
int rabin_miller(long long d, long long n) {
long long a = 2 + rand() % (n - 4);
long long x = modular_pow(a, d, n);
if (x == 1 || x == n - 1) {
return 1;
}
while (d != n - 1) {
x = (x * x) % n;
d *= 2;
if (x == 1) {
return 0;
}
if (x == n - 1) {
return 1;
}
}
return 0;
}
int isprime(long long n, int k) {
if (n <= 1 || n == 4) return 0;
if (n <= 3) return 1;
long long d = n - 1;
while (d % 2 == 0) {
d /= 2;
}
for (int i = 0; i < k; i++) {
if (!rabin_miller(d, n)) {
return 0;
}
}
return 1;
}
int main() {
long long n;
int k = 5; // 停止k次測試
printf("請輸入一個正整數：");
scanf("%lld", &n);
if (isprime(n, k)) {
printf("%lld是素數\n", n);
} else {
printf("%lld不是素數\n", n);
}
return 0;
}
總結