首页用c语言代码实现埃式筛法和欧拉筛法

用c语言代码实现埃式筛法和欧拉筛法

时间: 2024-12-04 08:26:18 浏览: 76

埃氏筛法（Sieve of Eratosthenes）是一种找出一定范围内所有质数的经典算法，它通过从2开始，每次将当前未标记的合数的倍数都标记为合数，直到遍历到平方根。下面是C语言实现的一个简单版本： ```c #include <stdio.h> #include <math.h> void eratosthenes(int n) { int prime[n+1]; for (int i = 0; i <= n; i++) prime[i] = 1; for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * p; i <= n; i += p) prime[i] = 0; } } printf("Prime numbers below %d are:\n", n); for (int p = 2; p <= n; p++) if (prime[p]) printf("%d ", p); } int main() { int n = 50; eratosthenes(n); return 0; } ``` 而欧拉筛法（Euler's Sieve）则更为高效，可以同时找出范围内的所有互质数。这里给出一个简化版的C代码实现： ```c #include <stdio.h> #include <stdlib.h> // Function to store sieve and count of co-primes #define MAX 1000001 int sieve[MAX], phi[MAX]; void eulersieve() { for (int i = 2; i < MAX; i++) { if (!sieve[i]) { for (int j = i; i*j < MAX; j++) { sieve[i*j] = 1; phi[i*j] += phi[j]; // phi(n) is sum of phi(p) for all primes p dividing n } phi[i] = i - sieve[i]; // phi(i) for prime 'i' } } } int main() { eulersieve(); int n = 50; printf("Prime numbers and their counts of co-primes below %d are:\n", n); for (int i = 2; i <= n; i++) { if (!sieve[i]) { printf("%d has %d co-primes\n", i, phi[i]); } } return 0; } ```

阅读全文