[C++知识库]C语言----求解N以内的素数的两种典型方法以及其优化

题目描述：求解N以内的素数

法一：（筛选法）

筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。?

?

#include <stdio.h>
int main()
{
    int arr[101]={0}; // 使数组下标和下标对应的值保持相同，数组不越界
    int n=0;
    while(scanf("%d",&n)!=EOF)  // 多组输入
    {
        int i=0;
        for(i=0;i<n;i++)
        {
            arr[i]=i;
        }
        for(i=2;i<=n;i++)
        {
            int j=0;
            for(j=i+1;j<=n;j++)
            {
                if(arr[j]%i==0)
                {
                    arr[j]=0;
                }
            }
        }
        int count=0; // 统计0的个数
        for(i=2;i<=n;i++)
        {
            if(arr[i]==0)
            {
                count++;
            }
            else
            {
                printf("%d ",arr[i]);
            }
        }
        printf("\n%d\n",count);
    }
    return 0;
}

法二：（试除法）

基础版本:

#include <stdio.h>
int is_prime(int i)
{
	int j = 0;
	for (j = 2; j < i; j++)
	{
		if (i%j == 0)
			return 0;
	}
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	for (i = 2; i <= n; i++)
	{
		if (is_prime(i))
			printf("%d ", i);
	}
	return 0;

优化版本1.0：（相关点在代码中以注释形式给出)

#include <stdio.h>
int is_prime(int i)
{
	int j = 0;
	for (j = 2; j < i; j++)
	{
		if (i%j == 0)
			return 0;
	}
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	for (i = 3; i <= n; i+=2)  // 可知，素数不可能是偶数，所以初始化全为奇数
	{
		if (is_prime(i))
			printf("%d ", i);
	}
	return 0;
}

优化版本2.0：

因为试除数 j? 写成两数乘积形式的话（能被 j 除尽的数也一定能被j的乘数除尽），其中一个数绝不会大于 试除数的开平方 ，所以可以直接对试除数开平方，这样在比较时候就可以节省一半效率，优化啦代码?（eg.16=2*8=4*4 可见，两个乘数都没有哪个比开平方4还大?）。

#include <stdio.h>
#include <math.h>
int is_prime(int i)
{
	int j = 0;
	for (j = 2; j < sqrt(i); j++)
	{
		if (i%j == 0)
			return 0;
	}
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	for (i = 3; i <= n; i += 2)
	{
		if (is_prime(i))
			printf("%d ", i);
	}
	return 0;
}

over~

本文长期更新，如果有了更优化的版本还会回过头继续更新 ~