自然数(Natural
Number)：自然数就是正整数集合，用{1, 2, 3,
...}表示，也可以是非负整数集合，用{0, 1, 2, 3,
...}表示，前都主要用于数论，后者则主要用于数理逻辑、集合论、计算机科学等。
素数(): 素数一个大于1的自然数，该自然数只有1和它本身两个除数（自然数）。
这概念虽然简单，但如果不知道的话程序写将无从下手，这无异于“James,
给我写个满足要求的程序", 但并没有说写什么样的程序。
典型算法
最简单最直接的方法应该就是用2到（n-1)的自然数去除n，其中n即为将要确实是数，如果每个数都不能整除，则说明n是素数。
而事实上没有必要用2到(n-1)之间的每一个数去除n。例如要确实7是不是系数，用除到3的时候就已经可以确实7是系数而不必继续了，即只要用2，3去除n就可以了。一般地，只要用2到n/2的自然数去除n就可以了。这样比前面的方法要快一点。
人们还想到了一个更好一点方法：用
来取代n/2。
今天同学考试的问题是：给定两个整数m,k，找出大于m同时也最靠近m的k个素数，用C语言实现如下，完整代码参见[7、程序实现]：
void
findPrimeNum(int m, int k , int xx[]) {
int i
= 0, j, x = m + 1, isPrime;
while (i < k)
{
isPrime =
TRUE;
for ( j = 2; j <=
sqrt(x); j++) { // j <= 2 也行
if ( x % j == 0 )
{
isPrime = FALSE;
break;
}
}
if (isPrime) xx[i++] =
x;
x++;
}
}
更有效的算法
如果给定一个很大的自然数要确定其是否为素数，典型算法可能要费很多的时间才能确定下来。这里有一个更好一点的算法：
boolean
isPrime(int num)
{
int divisor = 3;
int testLimit =
num;
if (num % 2 == 0) return
FALSE;
while ( testLimit > divisor )
{
if ( num % divisor == 0
) {
return FALSE;
}
testLimit = num /
divisor;
divisor +=
2;
}
return TRUE;
}
参考资源
[1]Prime
number, wikipedia,
http://en.wikipedia.org/wiki/Prime_number
[2]Determine if an
Integer is a prime number, Toby Herring, http://www.freevbcode.com/ShowCode.asp?ID=1059
程序实现
清单1：C实现
/*
*
典型算法
*/
#include
<stdio.h>
#include
<math.h>
#define MAX_LEN 100
#define
TRUE 1
#define FALSE 0
typedef int
boolean;
void findPrimeNum(int m, int k , int
xx[]);
void findPrimeNum2(int m, int k , int
xx[]);
int isPrime(int num);
int main(void)
{
int m, k, i, xx[MAX_LEN],
xx2[MAX_LEN];
printf("输入m: ");
scanf("%d",
&m);
do
{
printf("输入k (k < %d): ", MAX_LEN);
scanf("%d", &k);
}
while (k > MAX_LEN);
puts("运行及结果:");
findPrimeNum (m , k ,
xx);
findPrimeNum2 (m , k ,
xx2);
for (i = 0; i < k ; i++)
{
printf("%d, ",
xx[i]);
}
printf("\n");
for (i = 0; i < k ; i++)
{
printf("%d, ",
xx2[i]);
}
printf("\n");
puts("结束");
return
0;
}
void findPrimeNum(int m, int k ,
int xx[]) {
int i = 0, j, x = m + 1,
isPrime;
while (i < k)
{
isPrime =
TRUE;
for ( j = 2; j
<= sqrt(x); j++) { // j <= 2 也行
if ( x % j == 0 )
{
isPrime = FALSE;
break;
}
}
if (isPrime) xx[i++]
= x;
x++;
}
}
void findPrimeNum2(int m, int k , int
xx[]) {
int i = 0, j, x = m +
1;
while ( i < k)
{
if (isPrime(x)) xx[i++] = x;
x++;
}
}
boolean isPrime(int num)
{
int divisor = 3;
int testLimit =
num;
if (num % 2 == 0) return
FALSE;
while ( testLimit > divisor )
{
if ( num % divisor == 0
) {
return FALSE;
}
testLimit = num /
divisor;
divisor +=
2;
}
return
TRUE;
}
清单2：VB实现
Module
Module1
Sub
Main()
Dim num As
Long
num =
14
If (IsPrime(num))
Then
MsgBox(num & " is
Prime")
Else
MsgBox(num & " is NOT
Prime")
End
If
End
Sub
Public Function IsPrime(ByVal
TestPrime As Long) As
Boolean
Dim TestNum
As Long
Dim TestLimit
As Long
‘ Eliminate even
numbers
If TestPrime
Mod 2 = 0 Then Exit
Function
‘ Loop through ODD numbers starting with
3
TestNum =
3
TestLimit =
TestPrime
Do While
TestLimit >
TestNum
If TestPrime Mod TestNum = 0
Then
‘ Uncomment this if you really want to
know
‘MsgBox("Divisible by " &
TestNum)
Exit
Function
End
If
‘ There‘s logic to this. Think about
it.
TestLimit = TestPrime \
TestNum
‘ Remember, we only bother to check odd
numbers
TestNum = TestNum + 2
Loop
‘ If we made it through the loop, the number is a
prime.
IsPrime =
True
End Function
End
Module
原文：http://www.cnblogs.com/Hewie/p/3677468.html