c和指针习题四: 求素数的题目
程序代码:
#include <stdio.h> /* c和指针习题四: 质数就是只能被1和本身整除的整数,Eratosthenes筛选法是一种计算质数的有效方法 这个算法的第一步就是写下所有从2至某个上限的所有整数。在算法的剩余部分,你遍 历整个列表,并剔除所有不是质数的整数。以下省略N字。 编写一个程序,实现这个算法使用数组表示你的列表,每个数组元素的值用于标记对应 的数是否已经剔除,开始时数组所有元素都设置为true,当算法要求剔除该元素时,就 把这个元素设置为false。 要求:你可以使用下标来标记指向数组首元素和数组尾元素的指针,但应该使用指针来 访问数组元素。 */ //我设计的一个子函数,用于能够查找第N个TRUE的数组下标 int count_true(bool source[],int n,int sz_len) { int ret=-1; bool *p_begin=source; for(int i=0;i<sz_len;i++) { if(*p_begin==true) ret++; if(ret==n) { return i; } p_begin++; } return -1; } int main(void) { //数组元素代表的是 2..101;对应数组下标分别为i+2 bool source[100]; for(int i=0;i<100;i++) source[i]=true; int len=sizeof(source)/sizeof(source[0]); bool *p_begin=source; bool *p_begin2=source; bool *p_end=source+len; int first=0; int c_t=0; while(first!=-1) { int second=first+1; //从下一个true的下一个元素开始删除 p_begin+=second; while(*p_begin<*p_end) { if ((second+2)%(first+2)==0) *p_begin=false; //用于删除非素数元素 second++; p_begin++; } p_begin=p_begin2; first=count_true(source,c_t++,len); //查找下一个true } for(i=0;i<len;i++) { if(source[i]==1) printf("%4d",i+2); } return 0; }