求N之内的素数

求N之内的素数 1：一般思路

遍历2-N之内的所有数字，并依次判断是否为素数。

2：代码

#include
#include
int isPrime(int x)
{
    if(x<=1)
    {
        return 0;
    }else if(x==2)
    {
        return 1;
    }else
    {
        for(int i=2;i<=sqrt(1.0*x);i++)
        {
            if(x%i==0)
            {
                return 0;
            }
        }
        return 1;
    }
}
void findPrime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(isPrime(i))
        {
            printf("%dn",i);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    findPrime(n);
}

3:反思

以上代码比较繁琐，判断每一个数字时都需要从1遍历到这个数字的平方根，做了过多无用功。

4:改进

1：补充知识：算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

5：代码

#include
#define MAX 10000
int prime[MAX]={0};

void primeBiao()
{
	prime[0]=prime[1]=1;//代表0,1非质数
	for(int i=2;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711943.html