首页 > ACM题库 > HDU-杭电 > hdu 2161 Primes-数论-[解题报告]C++
2013
12-30

hdu 2161 Primes-数论-[解题报告]C++

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;
}

 

 

 

 

 

解题转自:http://blog.csdn.net/lulipeng_cpp/article/details/7698911


  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