【C语言用筛选法求质数】

C语言用筛选法求质数

筛选法，另一种思路的求质数方法

1. 上面的方法数越大判断次数越多，运算时间越长，效率越差，如果对于给定的一个集合，可以用筛选法，思路是将集合中的非质数（合数）标出来，余下来的就是质数了。
2. 给定的字符数组char prime[100] = {0};，初始化为0，默认全是质数:-)！
3. prime[0] = 1; prime[1] = 1; 0和1不是质数，标为1，2是质数，不动！
4. 大于2的偶数都不是质数，循环，赋值，标为1；
5. 大于1的奇数（从3开始，循环，每次加2）的大于1的倍数（从2开始，循环，每次加1）都不是质数，循环，赋值，标为1；
6. 以上操作后，数组中值为0的下标索引都是质数了，循环顺序输出即可！！！
7. 定义了一个宏PSIZE值为100，来限定集合范围！！！
   代码如下：

/* filename: prime.c */
#include <stdio.h>

/* compile : gcc prime.c -o prime
       run : ./prime               */

#define PSIZE 100

/**/
void
get_prime (void)
{
  char prime[PSIZE] = {0};

  prime[0] = 1; prime[1] = 1;

  for (int i = 2; i*2 < PSIZE; i++)
    prime[i*2] = 1;

  for (int i = 3; i < PSIZE / 3 + 1; i = i + 2)
    for (int j = 2; i*j < PSIZE; j++)
      prime[i*j] = 1;

  for (int i = 0; i < PSIZE; i++)
    if (0 == prime[i]) printf ("%d ", i);
  printf ("\n");
}

/**/
int
main (int argc, char *argv[])
{
  get_prime ();
  return 0;
}
/* --(:-O-:)-- */

编译运行，结果如下：

songvm@ubuntu:~/works/xdn$ gcc prime.c -o prime
songvm@ubuntu:~/works/xdn$ ./prime
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

与上一种方法在求100以内的质数时，结果相同

1. 将宏定义PSIZE改为100000仍可以运行，注意将输出结果代码注释掉（输出的数据太多太耗时）
2. 将宏定义PSIZE改为10000000时出错，编译时加-g选项，用gdb调试！！！
   结果如下：

songvm@ubuntu:~/works/xdn$ ./prime
段错误 (核心已转储)
songvm@ubuntu:~/works/xdn$ gcc -g prime.c -o prime
songvm@ubuntu:~/works/xdn$ gdb ./prime
GNU gdb (Ubuntu 8.1.1-0ubuntu1) 8.1.1
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./prime...done.
(gdb) r
Starting program: /home/songvm/works/xdn/prime 

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554728 in get_prime () at prime.c:15
15	  char prime[PSIZE] = {0};
(gdb) q
A debugging session is active.

	Inferior 1 [process 4680] will be killed.

Quit anyway? (y or n) y

发现问题出在第15行

char prime[PSIZE] = {0};

1. 字符数组初始化时出现问题，可能是数组空间太大，我们用分配释放内存的办法改造一下
   char prime = (char) malloc (PSIZE);
2. 用memset函数将分配的内存初始化为0
   memset (prime, 0, PSIZE);
3. 在函数运行最后将分配的内存释放掉
   free (prime);
4. 不再输出质数，用count计数，看一下结果
   代码如下：

/* filename: prime.c */
#include <stdio.h>
#include <stdlib.h> //for malloc and free
#include <string.h> //for memset

/* compile : gcc prime.c -o prime
       run : ./prime               */

#define PSIZE 10000000

/**/
void
get_prime (void)
{
  int count = 0;
  char *prime = (char*) malloc (PSIZE);
  memset (prime, 0, PSIZE);

  prime[0] = 1; prime[1] = 1;

  for (int i = 2; i*2 < PSIZE; i++)
    prime[i*2] = 1;

  for (int i = 3; i < PSIZE / 3 + 1; i = i + 2)
    for (int j = 2; i*j < PSIZE; j++)
      prime[i*j] = 1;

  for (int i = 0; i < PSIZE; i++)
    if (0 == prime[i]) count++;
  printf ("1 - %u : %d\n", PSIZE, count);
  free (prime);
}

/**/
int
main (int argc, char *argv[])
{
  get_prime ();
  return 0;
}
/* --(:-O-:)-- */

编译运行，通过！明显能感觉到停了一下！！！

songvm@ubuntu:~/works/xdn$ gcc -g prime.c -o prime
songvm@ubuntu:~/works/xdn$ ./prime
1 - 10000000 : 664579

再改造一下

• 依次输出1 - 100，1 - 1000，1 - 10000，1 - 100000区间的质数数量
  代码如下：

/* filename: prime.c */
#include <stdio.h>
#include <stdlib.h> //for malloc and free
#include <string.h> //for memset

/* compile : gcc prime.c -o prime
       run : ./prime               */

#define PSIZE 10000000

/**/
void
get_prime (void)
{
  int count = 0;
  char *prime = (char*) malloc (PSIZE);
  memset (prime, 0, PSIZE);

  prime[0] = 1; prime[1] = 1;

  for (int i = 2; i*2 < PSIZE; i++)
    prime[i*2] = 1;

  for (int i = 3; i < PSIZE / 3 + 1; i = i + 2)
    for (int j = 2; i*j < PSIZE; j++)
      prime[i*j] = 1;

  for (int i = 0; i < PSIZE; i++)
    {
      if (0 == prime[i]) count++;
      if (i == 100)
	printf ("1 - 100 : %d\n", count);
      else if (i == 1000)
	printf ("1 - 1000 : %d\n", count);
      else if (i == 10000)
	printf ("1 - 10000 : %d\n", count);
      else if (i == 100000)
	printf ("1 - 100000 : %d\n", count);
      else if (i == 1000000)
	printf ("1 - 1000000 : %d\n", count);
    }
  printf ("1 - %u : %d\n", PSIZE, count);
  free (prime);
}

/**/
int
main (int argc, char *argv[])
{
  get_prime ();
  return 0;
}
/* --(:-O-:)-- */

编译运行，结果和上一篇博文的结果一致！！！

1 - 100 : 25
1 - 1000 : 168
1 - 10000 : 1229
1 - 100000 : 9592
1 - 1000000 : 78498
1 - 10000000 : 664579

用valgrind来检查一下内存使用情况

• 在命令行中使用 valgrind
• 加参数 --leak-check=yes
• 加参数程序名 ./prime
  运行结果如下：

songvm@ubuntu:~/works/xdn/woo$ valgrind --leak-check=yes ./prime
==2668== Memcheck, a memory error detector
==2668== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2668== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2668== Command: ./prime
==2668== 
1 - 100 : 25
1 - 1000 : 168
1 - 10000 : 1229
1 - 100000 : 9592
1 - 1000000 : 78498
1 - 10000000 : 664579
==2668== 
==2668== HEAP SUMMARY:
==2668==     in use at exit: 0 bytes in 0 blocks
==2668==   total heap usage: 2 allocs, 2 frees, 10,001,024 bytes allocated
==2668== 
==2668== All heap blocks were freed -- no leaks are possible
==2668== 
==2668== For counts of detected and suppressed errors, rerun with: -v
==2668== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

• 等号中的数字是我们程序运行的进程的ID。
• 分配了两次，释放了两次，分配了10,001,024字节，我们代码中分配了10,000,000字节，系统为我们分配了1024字节，能看出来吧！
• 最后一行是出错信息，0表示没有！！！
• 如果有的话，请修改你的代码！！！

如何计时呢？下一步研究一下。