素数的求法
1.素数的定义
只能被1和它自己整除的自然数称为素数，特别规定1不属于素数。
2.求法
(1)根据素数的定义，很明显，如果一个数是素数<==>它的因子只包含1和它本身。
因此可以根据判别某个数的因子的方法来判断其是否是素数。
int
isprime(
int
n)
{
int i;
for (i = 2 ;i <= ( int )sqrt(( double )n);i ++ )
{
if (n % i == 0 ) // 如果n存在其它因子,则必定不是素数
{
return 0 ;
}
}
return 1 ;
}
{
int i;
for (i = 2 ;i <= ( int )sqrt(( double )n);i ++ )
{
if (n % i == 0 ) // 如果n存在其它因子,则必定不是素数
{
return 0 ;
}
}
return 1 ;
}
(2)但是如果要求求出1000000以内的所有素数，上面的方法效率就很低，因此通常采用筛选法去求素数。
筛选法：对于一个数n，如果是素数，那么2*n，3*n，4*n，必定不是素数。
bool
isprime[
1000001
];
int prime[ 80000 ];
int num = 0 ;
void getPrime() // 用筛选法求算素数
{
int i,j;
for (i = 0 ;i < 1000001 ;i ++ )
{
int prime[ 80000 ];
int num = 0 ;
void getPrime() // 用筛选法求算素数
{
int i,j;
for (i = 0 ;i < 1000001 ;i ++ )
{
if(i%2!=0)
isprime[i] = true ;
isprime[i] = true ;
else
isprime[i] = false;
}
for (i = 2 ;i <= 1000 ;i ++ ) // 如果isprime[i]==true,即i是素数，那么i，2*i，3*i必定不是素数
{
for (j = i + i;j <= 1000000 ;j += i)
{
if (isprime[i] == true )
isprime[j] = false ;
}
}
for (i = 2 ;i < 1000001 ;i ++ )
{
if (isprime[i] == true )
{
prime[num ++ ] = i;
}
}
}
}
for (i = 2 ;i <= 1000 ;i ++ ) // 如果isprime[i]==true,即i是素数，那么i，2*i，3*i必定不是素数
{
for (j = i + i;j <= 1000000 ;j += i)
{
if (isprime[i] == true )
isprime[j] = false ;
}
}
for (i = 2 ;i < 1000001 ;i ++ )
{
if (isprime[i] == true )
{
prime[num ++ ] = i;
}
}
}
