素数难题
1000ms
1000ms
65536KB
64-bit integer IO format: %lld Java class name: Main
Font Size:
数论是数学中重要的一个分支。著名的数学家高斯曾经说过一句经典名言：“数学是科学的皇后，而数论是数学的皇后”。由于近代计算机科学和应用数学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合论等方面都广泛使用了初等数论范围内的许多研究成果。在ACM/ICPC竞赛中也有很多和数论有关的知识和算法，我们学校的5l2大牛在这方面就造诣颇深。
数论中最基本、最重要的一类数是素数。一个大于1的正整数p，它除了1和它本身之外没有因子，就被称为是素数。（如果有某个整数c使得b=ac，那么称整数a是整数b的因子或除数）2，3，5，7，11，13，17，…这些数是素数，而比如说，12就不是，因为12=3×4。素数的重要性在于这样一个事实：每一个整数都能够表示为素数的乘积。如果一个数本身不是素数，那么可以不断地对它进行因子分解，直到所有的因子都是素数为止。例如360=32×23×5。一个非负整数（除了0和1），如果不是素数，就称为合数。
素数中有很多难题，很值得研究。有两个至今尚未解决的著名问题。一个叫哥德巴赫猜想，是由哥德巴赫在1742年给欧拉的信中提出来的。他由实验观察到，任何一个大于2的偶数，都能够表示成为两个素数的和。例如，4=2+2，6=3+3，8=5+3，…，100=97+3，…等等。哥德巴赫问欧拉，能不能证明这对于所有大于2的偶数都是成立的，或者证明是不成立的。欧拉没有给出回答，在那之后也还没有人给出回答。另外一个比哥德巴赫问题更加引人注目的问题是，以p和p+2形式出现的素数对是否是有无穷多对，在这个问题的研究上比哥德巴赫问题的进展还要少。
素数问题的研究，极大地推动了数论和数学的进步。现在我们来看一个基本的问题——素数判定。最朴素的方法是按照素数的定义来做——看它除了1和它本身之外是否还有因子，这种方法对于不太大的数是很方便的。除此之外，为了实现对大数的素性测试，数学家还提出了另外的一些素数测试方法，例如费马测试、米勒拉宾测试。
现在，请你写一个程序来判断一个数是不是素数。
Input
输入数据包含多行，每行一个数，N(1<=N<=1000)。N=0时输入结束，你的程序不需要处理它。
Sample Input
1 2 0
Sample Output
NO YES
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define M 1010
using namespace std;
int main()
{
int i,vit[1010],j,n;
memset(vit,0,sizeof(vit));
vit[1]=0;
vit[2]=1;
for(i=3; i<=M; i++)
{
if(i%2)
vit[i]=1;
else
vit[i]=0;
}
for(i=3; i<=M; i+=2)
{
if(vit[i])
{
for(j=i*2; j<=M; j+=i)
vit[j]=0;
}
}
while(~scanf("%d",&n)&&n)
{
if(vit[n])
printf("YES ");
else
printf("NO ");
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define M 1010
using namespace std;
int main()
{
int i,vit[1010],j,n;
memset(vit,0,sizeof(vit));
vit[1]=0;
vit[2]=1;
for(i=3; i<=M; i++)
{
if(i%2)
vit[i]=1;
else
vit[i]=0;
}
for(i=3; i<=M; i+=2)
{
if(vit[i])
{
for(j=i*2; j<=M; j+=i)
vit[j]=0;
}
}
while(~scanf("%d",&n)&&n)
{
if(vit[n])
printf("YES ");
else
printf("NO ");
}
return 0;
}