求素数的几种常见方法_如何求素数

求素数的几种常见的方法

素数

简单来说素数就是只能被1和它本身整除

求素数的方法

1.遍历法

遍历法就是从1开始，一个数一个数的来除以数字number，但我们可以从2开始，同时我们知道，2*3跟3*2是一样的，所以我们只需要考虑从2到sqrt(number)，（sqrt是求算术平方根）这样既可以简便一些还可以减少程序运行时间

代码如下（示例）：

#include <stdio.h>
#include <math.h>
int Isprime(int m)//如果是素数则返回1，否则返回0 
{
    int n;
    if(m%2==0)
    return 0;
    for(n=3;n<=sqrt(m);n+=2)
    {
        if(m%n==0)
        return 0;
    }
    return 1;
}
int main()
{
    int i,number;
    scanf("%d",&number);//输入数字number 
    for(i=2;i<n;i++)
    {
        if(Isprime(i))//条件为真，则打印数字 
        printf("%d ",i);
    }
}

2.筛选法

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

代码如下（示例）：

#include <stdio.h>
 
int main() 
 
{
 
    int number = 0;
 
    scanf("%d",&number);
 
    int i,j,arr[100];
 
    for(i=0;i<number-1;i++) //将2~number之间的正整数放在数组内
 
    {
 
        arr[i] = i+2;
 
    }
 
    int count = 1;
 
    for(j=2;j<=number;j++,count++)//设计一个count，是因为遍历的是arr[count]后面的数能不能被j整除，而不是遍历整个数组能不能被j整除
 
    {
 
        int k=0;
 
        for(k=count;k<number-1;k++) //求解素数，将能被整除是数清为0
 
        {
 
            if(arr[k]%j==0)
 
            {
 
                arr[k] = 0;
 
            }
 
        }
 
    }
 
    int a = 0;
 
    int score = 0;//计数器，计算不是素数的个数
 
    for(;a<=number-2;a++)
 
    {
 
        if(arr[a]!=0)
 
        {
 
            printf("%d ",arr[a]);
 
        }
 
        else
 
        score++;
 
    }
 
    printf("\n%d\n",score);
 
    return 0;
 
}

可能写的并不是太好，但还是应该可以看懂的吧