2013
12-30

# Primes

Write a program to read in a list of integers and determine whether or not each number is prime. A number, n, is prime if its only divisors are 1 and n. For this problem, the numbers 1 and 2 are not considered primes.

Each input line contains a single integer. The list of integers is terminated with a number<= 0. You may assume that the input contains at most 250 numbers and each number is less than or equal to 16000.

Each input line contains a single integer. The list of integers is terminated with a number<= 0. You may assume that the input contains at most 250 numbers and each number is less than or equal to 16000.

1
2
3
4
5
17
0

1: no
2: no
3: yes
4: no
5: yes
6: yes

AC代码：31MS

#include<iostream>
using namespace std;

const int MAX=16001;
bool prime[MAX];

void initial()
{
memset(prime,true,sizeof(prime));
prime[1]=prime[2]=false;

int i,j,tmp;
for(i=3;i<MAX;i++)
{
tmp=(i+1)/2;
for(j=2;j<=tmp;j++)
{
if(i%j==0)
{
prime[i]=false;
break;
}
}
}
}

int main()
{
initial();

int n,cas=1;

while(scanf("%d",&n) , n>0)
{
printf("%d: ",cas++);
if(prime[n])
printf("yes\n");
else
printf("no\n");
}

return 0;
}

1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience