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

Light紫星

如题，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

int  prime ( 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)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) (((nb) + CHAR_BIT - 1) / CHAR_BIT)
/*为便于理解宏声明，举一些简单的例子：

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

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

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

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

#define MAX 10000

int main()
{
    char bitarray[BITNSLOTS(MAX)];
    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;
}

猥琐的草泥马

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

sulin804

用 whitch   case 吧   

Light紫星

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

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

WorldElite丶

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

seemk

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

seemk

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

glgh

郝斌教程中的代码：

# 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;
}

回忆流年

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