弱弱的发一个判断素数的C语言源码、大家给看一下算法还能再优化吗、、

Light紫星 发表于 2014-11-13 21:54

如题，C语言写的，dev c++下编译运行，输出200以内的全部素数和素数个数，

顺便问一下，有没有好的计算圆周率的算法，我有个Python版本的，有时间发下源码。

#include<stdio.h>
int isprime(int n)
{
if(n==1) return 0;
if(n==2)return 1;
if(n%2==0) return 0;
for(int i=3;i*i<=n;i+=2)
{
if(n%i==0)return 0;
}
return 1;
}
main()
{
int s=0;
for(int i=1;i<=200;i++)
{
if(isprime(i)==1)
{
s++;printf("%5d",i);
}
}
printf("\n%d ",s);
}

yahwei 发表于 2014-11-18 09:21

本帖最后由 yahwei 于 2014-11-18 09:54 编辑

intprime ( int n )
{
int s = 0;
if(n<=1) {
return 0;
}
if(n==2) {
printf("%d", n);
return 1;
}
for(int i=3;i*i<=n;i+=2) {
if( n % i!= 0 ){
   s += 1;
   printf("%d", i);
}
}
return s;
}
将素数个数s作为函数值返回，可以省去频繁调用函数的时间开销。
这种算法在范围n不大的时候效率还算可以，当n很大的时候可以考虑位数组，用 Sieve of Eratosthenes 算法求素数：
/*
**下面是位数组要用到的宏声明
*/
#include <limits.h>    /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a) |= BITMASK(b))
#define BITCLEAR(a, b) ((a) &= ~BITMASK(b))
#define BITTEST(a, b) ((a) & BITMASK(b))
#define BITNSLOTS(nb) (((nb) + CHAR_BIT - 1) / CHAR_BIT)
/*为便于理解宏声明，举一些简单的例子：

**声明一个固定长度（50个bit）的位数组：
**char bitarray;

**设置位数组中的某一位：
**BITSET(bitarray, 23);

**检测某一位
**if(BITTEST(bitarray, 35)) ...
*/

/*
**下面是完整例子
*/
#include <stdio.h>
#include <string.h>

#define MAX 10000

int main()
{
char bitarray;
int i, j;

memset(bitarray, 0, BITNSLOTS(MAX));

for(i = 2; i < MAX; i++) {
   if(!BITTEST(bitarray, i)) {
         printf("%d\n", i);
         for(j = i + i; j < MAX; j += i)
            BITSET(bitarray, j);
   }
}
return 0;
}

猥琐的草泥马 发表于 2014-11-13 22:10

虽然不懂，但是很吊的样子。。

sulin804 发表于 2014-11-14 08:06

用 whitch case 吧

Light紫星 发表于 2014-11-14 08:12

ubuntu 发表于 2014-11-13 22:18
另外，如果判断的数量比较多，可以先弄个数组，存入较小的素数，这样检测就可以跳过很多数字。
比如200以 ...

本来是判断20万以内的，200万以内的这个秒就能算出来，i*i那个地方就是sqrt的、

WorldElite丶 发表于 2014-11-14 12:51

差不多都是一样的，小程序体现不出什么的

seemk 发表于 2014-11-19 11:20

指数判断无非就是整数的分解,我所知道的有Miller-Rabin 算法和Pollard Rho算法,实现原理基于费马小定理:如果p是素数，则a^(p-1)≡1(mod p)对所有的a∈成立。所以如果在中随机取出一个a，发现不满足费马小定理，则证明n必为合数。可能还有一些椭圆曲线法，连分数法，二次筛选法，数域分析法等等,我不是很了解.不过肯定都要比暴力试除快.

seemk 发表于 2014-11-19 11:22

不过不管什么算法,复杂度都是指数级增长,没有基于公式的秒算方法,目前大整数的分解依然是世界级难题

glgh 发表于 2015-2-13 21:23

郝斌教程中的代码：

# include <stdio.h>

bool IsPrime(int val)
{
int i;

for (i=2; i<val; ++i)
{
if (val%i == 0)
break;
}
if (i == val)
return true;
else
return false;
}

int main(void)
{
int m;

scanf("%d", &m);
if ( IsPrime(m) )
printf("Yes!\n");
else
printf("No!\n");

return 0;
}

回忆流年 发表于 2015-2-13 21:36

把代码中的for替换成while，while的运算速度比for快，小程序看不出来

页: [1] 2

吾爱破解 - 52pojie.cn's Archiver

弱弱的发一个判断素数的C语言源码、大家给看一下算法还能再优化吗、、