判断一个数是否为质数4种方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了判断一个数是否为质数4种方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先理解什么是质数：

素数就是质素，只能被1和它本身整除的数字。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

最小的质数为2；

判断一个数是否为素数，要在2~i-1的数字去试除。如果i被整除，就说明i不是素数。如果2~i-1之间的数字都不能整除i，说明i是素数。

假设要计算100——200之间的素数

一.

#include<stdio.h>
int main()
{
    int i = 0;
    for (i = 100; i <= 200; i++)
    {
        int j = 0;
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                break;
            }
        }
        if (i==j)
        {
            printf("%d ", i);
        }
    }
    return 0;
}

第一种方法是最容易想到和理解的；

判断一个数是否为质数4种方法

二.

#include<stdio.h>
int main()
{
   int i = 0;
   for (i = 100; i <= 200; i++)
   {
       int flag = 1;//假设i为素数，定义一个标记，flag=1，则i为素数
       int j = 0;
       //判断i是否为素数
       for (j = 2; j < i; j++)
       {
           if (i % j == 0)
           {
               flag = 0;//被整除，可以被除尽，说明i不是素数
               break;
           }
       }
       if (1==flag)/i不能被整除则说明i是素数，如果if(1==flag)可执行，说明i是素数
       {
           printf("%d ", i);
       }
   }
   return 0;
}

判断一个数是否为质数4种方法

三.

c=a*b a和b中至少有一个数是小于等于开平方c

//16=2*8=4*4

sqrt函数是开平方函数

#include<stdio.h>
#include <math.h>
int main()
{
    int i = 0;
    for (i = 100; i <= 200; i++)
    {
        int flag = 1;
        int j = 0;
        for (j = 2; j < sqrt(i); j++)
        {
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        }
        if (1==flag)
        {
            printf("%d ", i);
        }
    }
    return 0;
}

判断一个数是否为质数4种方法

四.质数肯定不能被2整除，所以for循环结构可以优化

#include<stdio.h>
#include <math.h>
int main()
{
    int i = 0;
    for (i = 100; i <= 200; i+=2)
    {
        int flag = 1;
        int j = 0;
        for (j = 2; j < sqrt(i); j++)
        {
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        }
        if (1==flag)
        {
            printf("%d ", i);
        }
    }
    return 0;
}

判断一个数是否为质数4种方法