素数系列—判断素数 | LSABLOG

首页 » Program » C/C++ » 正文

素数系列—判断素数

何为素数?只能被1和自己整除的大于1的自然数。
最简单的方法就是用n去除2~n-1的数,如果余数有为0的就不是素数,否则就是素数。

#include <stdio.h>
int main()
{
    int n,i,flag;
    while (scanf("%d",&n)!=EOF&&n)
        {
            flag = 0;
            if (n==1)
                {
                    printf("NO\n");
                    flag = 1;
                }
            for (i=2; i<=n-1; i++)
                {
                    if (n % i==0)
                        {
                            printf("NO\n");
                            flag = 1;
                            break;
                        }
                }
            if (flag==0) printf("YES\n");
        }
    return 0;
}

优化:
用2~sqrt(n)去除就可以了,因为任何一个数的最大因子都小于等于此数的平方根。

赞 (0)

Comment