【C语言】筛法求素数以及其他

浏览数：23 / 时间：2015年06月08日

《algorithm：c》在第一节就介绍了求素数的方法，书中只涉及了筛法求素数，实际而言，还有其他一些方法，相比筛法，虽然效率不高，但也是很巧妙的，从这些方法的对比中，可发见一种思维的乐趣。具体地思路介绍，请看：http://program-think.blogspot.com/2011/12/prime-algorithm-1.html

代码请看：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <stdio.h>
#include <math.h>
 
 
#define N  3000
 
int 
isPrim(int 
n);
int 
isPrimBasic(int 
n);
int 
isPrimSqrt(int 
n);
void 
setOne(int 
c[], int 
bitpos);
 
#if 1  // 筛选求素数
int 
main()
{
    int 
i, j, a[N+1];
    int 
c[N/2+1];
    int 
b;
    int 
temp = 0x01;
 
    for(c[1] = 0, i = 2; i <= N/2; i++)
        c[i] = 0;
 
    for(a[1] = 0, i = 2; i <= N; i++)
        a[i] = 1;
    for(i = 2; i <= N/2; i++)
        for(j = 2; j <= N/i; j++)
            a[i*j] = 0;
 
    for(i = 1; i <= N; i++)
        if(a[i])
            printf("%6d", i);
    printf("\n");
 
/* 按位存储素数，没做出来
    for(i = 2; i <= N/4; i++)
        for(j = 2; j <= (N/2)/i; j++)
            setOne(c, i*j);
    for(i = 1; i <= N/2; i++)
    {
        for(j = 0; j < sizeof(int)*8; j++)
        {
            temp = 0x01;
            temp = temp << j;
            if( !(c[i] & temp ) )
                printf("%d\n", i*sizeof(int)*8+j);
        }
    }
*/
    printf("\n");
 
    while(scanf("%d", &b) != EOF)
    {
        if(isPrim(b))
            printf("素数\t%d\n", b);
 
        if(isPrimSqrt(b))
            printf("素数 sqrt\t%d\n", b);
    }
 
 
    return 
0;
}
#endif
 
void 
setOne(int 
c[], int 
bitpos)
{
    int 
i = 0x01;
    i = i << bitpos%(sizeof(int)*8);
    c[bitpos/(sizeof(int)*8)] = c[bitpos/(sizeof(int)*8)]  | i;
}
 
int 
isPrim(int 
n)
{
    int 
i;
 
    if( 1 == n || 2 == n)
        return 
1;
 
    if( n%2 == 0)
        return 
0;
 
    for(i=3; i < n/2; i+=2)
        if(n%i == 0)
            return 
0;
 
    return 
1;
}
 
int 
isPrimSqrt(int 
n)
{
    int 
i;
 
    if( 1 == n || 2 == n)
        return 
1;
 
    if( n%2 == 0)
        return 
0;
 
 
    for(i = 3; i <= (int)sqrt((double)n); i+= 2)
        if(n%i == 0)
            return 
0;
 
    return 
1;
}
         
int 
isPrimBasic(int 
n)
{
    int 
i;
 
    for(i = 2; i < n; i++)
        if(n%i == 0)
            return 
i;
 
    return 
1;
}