大哥，深了

前段时间看到一个高人，写的这个程序，当场给我写出来，加上输出，总共才6行代码。C++写的。。。。。。我差点没晕死

赞~~~终于有人意识到算法的重要性了,握个手先....

随便说一下,上面老师用的是厄氏筛法,在求素数表时很有用.
另外如果想快速判断一个数是否素数,可以考虑用蒙特卡罗随机算法,不过要牺牲一点点的准确性.

最初由 nbw 发布
大哥，深了

前段时间看到一个高人，写的这个程序，当场给我写出来，加上输出，总共才6行代码。C++写的。。。。。。我差点没晕死

要不要把代码贴出来,我回去给老师交差

最初由 fchker 发布
今天上午到学校培训,老师让我们用QBasic写一个程序,可以算出2到10000的所有质数,我是这样写的
FOR n = 2 TO 10000
k = 1
FOR i = 2 TO n - 1
IF (n MOD i) = 0 THEN
........

这种方法肯定很慢了,应该用剔除法.

水平不行啊,费了好大劲才压缩到七行,还不算末尾那个大括号

#include <stdio.h>
int prime[20000];
void main() {
	int tmp,i=2;
	while ((tmp=i)<20000) 
		if ((!prime[i++]) && (printf("%8d",i-1))) 
			while ((tmp+i-1)<20000) prime[tmp+=i-1]=1;
}

C,VC++6.0下编译通过

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#define NUMBER 500        //要求的素数范围的上界

void main()

{

       int number;                        

       int i = 0;                              //用于统计素数的个数

       int j ;                                   //被除数

       int num[NUMBER] = {0};    // num[i]表示整数i,如果为0表示为素数，为1表示是合数

       int *p = num;                      // 指向num的指针

       int N = (int)sqrt(NUMBER);      

       // 筛选所有偶数，即将数组元素置为 1，但将2排除在外

       for ( number = 2 ; number< NUMBER ; number += 2)

                     *(p + number + 2) = 1;                            //将不是素数的筛选掉

       // 筛选被能其他奇数整除的数

       for(j = 3 ; j < N ; j += 2)

       {

              // 筛选被j整除的数

              // number从j开始，表示不将j设置为非素数

              // number< NUMBER - j，否则*(p + (j + number))最后会越界

              for ( number = j ; number< NUMBER - j ; number += j)

              {

                     *(p + (j + number)) = 1;                    //将不是素数的筛选掉

              }

       }

      

       // 输出没被筛选掉的数，数组元素为0的，即素数

       for ( j = 2  ; j< NUMBER ; j ++)

       {

              if (*(p + j) == 0 )

              {

                     i++;

                     printf("%d\t",j);

                     // 10个以行

                     if (i%10 == 0)

                            printf("\n");

              }

       }

       printf("\n从1到%d一共有 % d个素数。\n",NUMBER,i);

}

最初由 RoBa 发布
水平不行啊,费了好大劲才压缩到七行,还不算末尾那个大括号
[code]
#include <stdio.h>
int prime[20000];
void main() {
........

你这个不错。人家开始就是给我演示的这个。这种很标准，效率不错，也便于别人看。不过人家说，搞点小技巧，可以更搞提高效率，然后把那个循环条件里面加了一个乘法，果然快了很多，可惜我还没理解了，他就删了。。。。。。

这个包含头文件共6行,不过我觉得这样牺牲可读性不值得.而且效率也不见得有提高.

#include <stdio.h>
int prime[20000];
void main(){int tmp, i = 2;
  while ((tmp = i) < 20000 )
    if ((!prime[i++]) && (printf("%8d", i - 1)))
      while ( ((tmp + i - 1) < 20000) && (prime[tmp += i - 1] = 1));}

    都是高人!!

最初由 backer 发布
这个包含头文件共6行,不过我觉得这样牺牲可读性不值得.而且效率也不见得有提高.

#include <stdio.h>
int prime[20000];
void main(){int tmp, i = 2;
........

  

晕,这样的写法,2行都写的出!
如果使用的是TC 可以去掉包含文件,一行就可以了!

那应该是什么规则?

高手们,我都晕死了

偶也只会穷举

这个算法真好，简单高效

晕倒   居然看到这种贴了   黄金含量高
唉   为自己一声叹息

呵呵,hunter_boy兄是什么意思阿

我用剔除法，1～1000000，1.5秒左右就可以了。

nbw说的很对 就6行代码 我绝对可以保证

Sieve of Eratosthenes
Eratosthenes
公元前276-公元前196
古埃及天文学家,地理学家,诗人

"Eratosthenes之筛" 千年前就有的

在vb里250毫秒

Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Sub Command1_Click()
Dim tt As Long
Dim n As Long
Dim k As Long
tt = GetTickCount()
For n = 2 To 10000
k = 1
For i = 2 To Sqr(n)
  If (n Mod i) = 0 Then
   k = 0
   Exit For
  End If
Next
If k = 1 Then
   Print n;
End If
Next
MsgBox (GetTickCount() - tt) & "毫秒"
End Sub

在vb里203毫秒

Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Sub Command1_Click()
Dim tt As Long
Dim n As Long
Dim k As Long
Dim i As Long
tt = GetTickCount()
For n = 2 To 10000
    k = Sqr(n)
    For i = 2 To k
        If (n Mod i) = 0 Then
            Exit For
        End If
        If Abs(i - k) < 1 Then
            Print n;
        End If
    Next i
Next n
MsgBox (GetTickCount() - tt) & "毫秒"
End Sub

在程序中算法是不可少的，一个好的程序必有一个或多个好的算法
我想请老大们，讲一讲目前所流行的算法！
再这谢了！

#include <stdio.h>

#define  MAX_LEN 100000
int main()
{
        bool numbers[1+MAX_LEN];
        int i=1;
    int j=1;

        for(i=1;i<=MAX_LEN;i++)
                numbers[i]=false;

        for(i=2;i<=MAX_LEN;i++)
                if(!numbers[i])
                {
                        j=2;
                        while(i*j <=MAX_LEN)
                        {
                                numbers[i*j]=true;
                                j++;
                        }
                }
   
        freopen("out.txt","w",stdout);

        for(i=1;i<=MAX_LEN;i++)
                if(!numbers[i])
                        printf("%d\n",i);
   
        return 0;
}

点击下载附件：
用vb编的
如果还有更快的程序，可以交流。