- //
- // main.m
- // 寻找质数
- //
- // 输入一个整数,列出从2到这个数的所有质数
- //
- /**
- 思路:
- 1. 首先 可以知道前3个质数为2,3,5
- 2. 5以后的偶数肯定都不是质数 所以后面用之前求出来的质数+2 在算这个数是不是质数
- 3. 算是不是质数的时候没必要遍历1-这个数,每次都除一遍 只需 遍历之前求出的所有质数就可以了
- */
- #import <Foundation/Foundation.h>
- int main()
- {
- long *p = NULL; //指向质数存储区域的指针
-
- int total = 0; //要寻找的质数个数
- bool found = false; //是否找到质数
- //提示用户输入一个整数
- printf("你需要寻找多少个质数:(至少要4个)\n");
- scanf("%d",&total);
- //至少4个 如果小于4 就设置总数为4个
- total = total < 4? 4: total;
-
-
- //分配足够的内存 给质数区域
- p = (long*)malloc(total*sizeof(long));
- //没有分配内存 直接退出函数
- if (p == NULL)
- {
- printf("连个内存都分配不出来,还做怎么啊!!!\n");
- return 1;
- }
- //我们已经知道了前3个质数
- *p = 2l;
- *(p + 1) = 3l;
- *(p + 2) = 5l;
-
- //寻找到的质数个数
- int count = 3;
- //测试的整数
- long trial = 5l;
- //开始寻找质数
- while (count < total)
- {
- trial += 2l;
- for (int i = 0;i < count ; i++)
- {
-
- if (!(found = trial % *(p+i)))
- {//遍历过程中有一次能被整除 就退出循环
- break;
- }
- }
-
- if (found)//遍历完毕后 trial 不能被它之前的质数整除
- {
- *(p + count++) = trial;//将找到的trail加入我们的质数库 质数数量+1
- }
- }
- //打印质数
-
- printf("以下为我们找到的%d个质数:\n",total);
- for (int i = 0 ; i<total; i++)
- {//输出找到的质数 左对齐 占12个字符
- printf("%-12ld",*(p+i));
-
- if ((i+1)%6==0)
- {
- //每6个换一次行
- printf("\n");
- }
- }
- return 0;
- }
复制代码 |
|