7.24 素数总结

判断素数：

第一种方法用于小数据。

 1 int k=0;
 2 int isprime(int num)
 3 {
 4      int i, j;
 5      j = sqrt(num);
 6      for (i = 2; i <= j; i++)
 7           if (num%i == 0)
 8             return 0;
 9      return 1;
10 }

第二种素数筛选：

用于大数据，数据很小的话就用第一种吧

1　　建立一个全1的数组(下标2~N),

2　　先将下标是2的倍数的全置0，再将下标是3的倍数全置0,……，以此类推，

3　　最后剩下的，仍是1的那些下标，就肯定是素数了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 
 5 #define N   100000
 6 #define yes '1'
 7 #define no  '0'
 8 char flag[N+1];
 9 
10 void is_prime(int n)
11 {
12     int i, j;
13     memset(flag, yes, sizeof(flag));
14     flag[0]=flag[1]=no;
15     int len=sqrt(n)+1;
16     for(i=2; i<len; i++)
17     {
18         if(flag[i]==no) continue;
19         for(j=i+i; j<=n; j+=i)
20             flag[j]=no;
21     }
22 }
23 
24 int main(void)
25 {
26     int n;
27     ///find the primes from 1 to n(n<=N)
28     scanf("%d", &n);
29     is_prime(n);
30     for(int i=1; i<=n; i++)
31         if(flag[i]==yes)
32             printf("%8d", i);
33     printf("
");
34     return 0;
35 }

素数打表：

 1 #define N   1000001
 2 #define yes '1'
 3 #define no  '0'
 4 char flag[N];
 5 int p[80000];
 6 void is_prime()
 7 {
 8     int i, j ;
 9     memset(flag, yes, sizeof(flag));
10     flag[0]=flag[1]=no;
11     int len=sqrt(N)+1;
12     for(i=2; i<len; i++)
13     {
14         if(flag[i]==no) continue;
15         for(j=i+i; j<=N; j+=i)
16             flag[j]=no;
17     }
18  
19     for (i=2;i<=N;i++)
20         if (flag[i]==yes)
21         {
22             T++;
23             p[T]=i;
24         }
25 }

总结：对于素数的题目，几乎都会用到前面三种。但素数表还是自己写吧。背下来的迟早会忘。至少要自己写的出来。