c语言欧拉筛法求素数 #欧拉筛法 #c语言

筛选一个小范围内的素数大家基本都会用遍历法，如筛选1~100的素数，大家可能会写出下面代码：

#include <stdio.h>
#include <math.h>

int main() {
    int num;
    for (num = 2; num <= 100; num++) {  // 遍历2到100的数
        int i;
        int is_prime = 1;  // 先假设是素数，标记为1
        for (i = 2; i <= sqrt(num); i++) {  // 从2到该数的平方根进行判断
            if (num % i == 0) {
                is_prime = 0;  // 如果能被整除，说明不是素数，标记为0
                break;
            }
        }
        if (is_prime == 1) {  // 根据标记判断是否为素数，若是则输出
            printf("%d ", num);
        }
    }
    return 0;
}

 但当我们求1~n,并且n 趋于无穷时，这个方法可能就会超时了，那有没有更高级的算法吗？

 当然有，欧拉筛法就是其中之一，但此算法过于复杂，下面我来为大家详细讲解一下。

      我们知道素数乘素数等于合数，所以我们可以用前面的素数相乘筛选出后面的合数，如图我们以2开始，2乘以2筛出4，

接下来用3乘以2筛出6，3乘以3筛出9，

接下来用4乘以2筛出8，  （合数乘以素数或者合数还是合数，于是当轮到合数只相乘到它的非1最小因子即停止）（例如4的因子有1，2，4.  6的因子有1，2，3，6，9的因子有1，3，9）

接下来用5乘以2筛出10，5乘以3筛出15，5乘以5筛出25，

依次推下去，没筛出的即为素数。

  于是我们可以设数组a[10000]为 初始数组，数字is_prime[10000]为素数数组

#include<stdio.h>
#define N 10000
int main()
{
	int i, j=0, k;
	int a[N] = { 0 }, is_prime[N] = { 0 };   //令数组初始化为 0，i为合数时，令a[i]=1
	for (i = 2; i <= N; i++) {             
		if (a[i] == 0) is_prime[j++] = i;    //当a[i]不为零时，将i保存到is_prime数组中
		for (k = 0; is_prime[k] <= N && i * is_prime[k] <= N; k++) {
			a[i * is_prime[k]] = 1;      //用前面的素筛出后面的合数
			if (i % is_prime[k] == 0) break;    //合数筛选停止条件，这步比较难理解
		}
	}
	for (i = 0; i < j; i++) {
		printf("is_prime[%d]=%d\n", i, is_prime[i]);
	}
	return 0;
}

最后打印结果如下：

最后麻烦各位大佬们留下手中三连，嘻嘻！！