素数判断:
一、根据素数定义，该数除了1和它本身以外不再有其他的因数。
详见代码。
int prime()
{
for (int i=; i*i<=n; i++)
{
if (n%i==) //不是素数
return ; //返回1
}
return ; //是素数返回0
}
二、打表，将所有的素数一一列出，存在一个数组里。
详见代码。
void prime()
{
for (int i=; i<; i++) //从2开始一个一个找
{
if (hash[i]==) //这一个判断可以减少很多重复的，节省很多时间
{
for (int j=; i*j<; j++) //只要乘以i就一定不是素数
{
hash[i*j]=; //不是素数标记为1
}
}
}
}
提供一种技巧、如果题目里面所有的计算都是素数之间的转化的话、可以如下。
void prime()
{
int k=;
for (int i=; i<; i++)
{
if (hash[i]==)
{
sushu[k++]=i; //所有的素数都存在了sushu的数组里面,或者放在队列里面q.push(i);
for (int j=; i*j<; j++)
{
hash[i*j]=;
}
}
}
}
举个例子：hdu2710 Max Factor
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2710
Max Factor
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4168 Accepted Submission(s):
1366
labels each of his N (1 <= N <= 5,000) cows with a distinct serial number
in the range 1..20,000. Unfortunately, he is unaware that the cows interpret
some serial numbers as better than others. In particular, a cow whose serial
number has the highest prime factor enjoys the highest social standing among all
the other cows.
(Recall that a prime number is just a number that has no
divisors except for 1 and itself. The number 7 is prime while the number 6,
being divisible by 2 and 3, is not).
Given a set of N (1 <= N <=
5,000) serial numbers in the range 1..20,000, determine the one that has the
largest prime factor.
* Lines 2..N+1:
The serial numbers to be tested, one per line
there are more than one, output the one that appears earliest in the input
file.
题目大意：找到所给数的最大素因子，然后在比较这些素因子的大小，找到最大的，最后输出原有的那个数。
详见代码。
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int hash[]; void prime()
{
for (int i=; i<; i++)
{
if (hash[i]==)
{
for (int j=; i*j<; j++)
{
hash[i*j]=i;//i表示的是最大的素因子
}
}
}
//return hash[n];
} int main ()
{
int T;
memset(hash,,sizeof(hash));
sushu();
while (~scanf("%d",&T))
{
int Max=,x=;
while (T--)
{
int n;
scanf("%d",&n);
if (hash[n]>Max)
{
Max=hash[n];
x=n;
}
}
printf ("%d\n",x);
}
return ;
}
最大公约数（gcd）
详见代码。
int gcd(int a,int b)
{
return a%b?gcd(b,a%b):b;
}
最小公倍数
求解最小公倍数，一般都要借助最大公约数。辗转相除求得最大公约数，再用两数之积除以此最大公约数，得最小公倍数。
注意基本！！！