今天上午到学校培训,老师让我们用QBasic写一个程序,可以算出2到10000的所有质数,我是这样写的
FOR n = 2 TO 10000
 k = 1
 FOR i = 2 TO n - 1
  IF (n MOD i) = 0 THEN
   k = 0
  END IF
 NEXT i
 IF k = 1 THEN
   PRINT n;
 END IF
NEXT n
这算是最简单的求质数的算法了,在我的P42.5上大概用了2分钟 
看我老师的
n = 10000
DIM arr(n)
FOR i = 2 TO SQR(n)
 IF arr(i) = 0 THEN
   FOR j = i * i TO n STEP i
      arr(j) = 1
   NEXT j
 END IF
NEXT i
FOR k = 1 TO n
  IF arr(k) = 0 THEN
  PRINT k;
  END IF
NEXT k
这个在学校P3 800MHz上瞬间算出  
由此可以看出算法的重要性

  • 标 题: 答复
  • 作 者:RoBa
  • 时 间:2005-03-06 13:20

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

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

  • 标 题: 答复
  • 作 者:RoBa
  • 时 间:2005-03-06 14:06

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

代码:
#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下编译通过

  • 标 题: 答复
  • 作 者:exe
  • 时 间:2005-03-06 14:09

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

}

  • 标 题: 答复
  • 作 者:menglv
  • 时 间:2005-05-15 13:31

在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

  • 标 题: 我使用的排除法 ,(欢迎交朋友交流算法)
  • 作 者:TY_JNU
  • 时 间:2005-05-20 18:19

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

  • 标 题: 答复
  • 作 者:RoBa
  • 时 间:2005-06-18 17:41

sooooooooo many ,看你想要哪一方面的了

举几个例子吧:

比如关于图的算法,常见的有 
深搜(DFS),广搜(BFS),拓扑排序
最短路径的dijkstra,bellman-ford,floyd
最小生成树的prim,kruskal
网络流的Ford-fulkerson
等等等等

再比如排序,简单的有选择排序,冒泡排序,复杂些的有堆排序,归并排序,快速排序,还有不是基于比较的如基数排序,桶排序等等,这还没有包括情况更加复杂的外部排序.

还有一些是比较重要的算法设计思想,并不具体固定在某个算法上,但却又无处不在,如 贪心,动态规划,分治 等等.

不知道这些是不是算流行,但肯定是应用最广的.

  • 标 题: 算到2563200,如果不输出不到1秒
  • 作 者:menglv
  • 时 间:2005-06-19 18:23

25楼的源程序,不用开方的。
我实在没办法再进一步优化了。
如果算到1001990,仅需282毫秒!!!

Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Sub Command1_Click()
Dim a(200000) As Long
Dim tt As Long
Dim n As Long
Dim k As Long
Dim i As Long
Dim j As Long
Dim a1 As Long
Dim a2 As Long
Dim k1 As Long
Dim l As Long
aa = 1 - Check1.Value
tt = GetTickCount()
a(0) = 2
a(1) = 3
a1 = 4
k = 1
k1 = 1
For n = 2 To 1600
    a2 = a1 + n + n + 1
    If n > a(k) Then k = k + 1
    l = n Mod 2
    For i = a1 + 1 + l To a2 - 2 + l Step 2
        For j = 1 To k
            If i Mod a(j) = 0 Or i = 1 Then Exit For '去掉Or i = 1更慢?
            
            If j = k Then
                k1 = k1 + 1
                a(k1) = i
            End If
        Next
    Next
    a1 = a2
Next
If aa = 1 Then
Cls
Print "第" & k1 + 1 & "个素数为"; a(k1)
MsgBox (GetTickCount() - tt) & "毫秒"
Else
Open "li.txt" For Output As #1
For i = 0 To k1
    Print #1, "第" & i + 1 & "个素数为"; Tab(20); a(i)
Next
MsgBox (GetTickCount() - tt) & "毫秒"
Close
End If
Erase a()
End Sub

  • 标 题: 答复
  • 作 者:microsoftxiao
  • 时 间:2005-11-19 22:53

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int m,n;
    int i,j;
    scanf("%d%d",&m,&n);
    if(m>n)return 0;
    while(i<=n){
       j=2;
       while(j<=i-1){
           if(i%j==0)break;
           j++;
       }
       if(j>=i)printf("%5d",i);
       i++;
    }
    printf("\n");
    system("pause");
    return 0;
}

  • 标 题: 答复
  • 作 者:lotusroots
  • 时 间:2005-11-30 14:56

无聊中,
所以,过来看看。

记得要跳过2的倍数可以减少一半的时间。既然上面的兄弟使用vb写,那么,我也写vb的。
所以,代码如下:

Private Sub Command2_Click()
    Const max = 1001989
    
    Dim prime(max) As Long
    Dim i As Long
    Dim tt As Long
    
    For i = 0 To max
        prime(i) = 1
    Next
    
    Dim current As Long
    Dim dCurrent As Long
    Dim temp As Long
    
    tt = GetTickCount
    current = 3
    While current <= max
        If prime(current) = 1 Then
            dCurrent = current * 2
            temp = current + dCurrent
            While temp < max
                prime(temp) = 0
                temp = temp + dCurrent
            Wend
        End If
        current = current + 2
    Wend
    Dim primeNum As Long
    primeNum = 1
    For i = 3 To max Step 2
        If prime(i) = 1 Then primeNum = primeNum + 1
    Next i
    MsgBox "PrimeNum:" + Str(primeNum) + " Time:" + Str(GetTickCount - tt)
End Sub

计算到1001989,使用时间120ms。

还有一个对3不进行计算的代码:

Private Sub Command2_Click()
    Const max = 2600000
    
    Dim prime(max) As Long
    Dim i As Long
    Dim tt As Long
    
    For i = 0 To max
        prime(i) = 1
    Next
    
    Dim current As Long
    Dim dCurrent As Long
    Dim temp As Long
    
    tt = GetTickCount
    current = 1
    While current <= max - 6
        current = current + 4
        If prime(current) = 1 Then
            dCurrent = current * 2
            temp = current + dCurrent
            While temp <= max
                prime(temp) = 0
                temp = temp + dCurrent
            Wend
        End If
        current = current + 2
        If prime(current) = 1 Then
            dCurrent = current * 2
            temp = current + dCurrent
            While temp <= max
                prime(temp) = 0
                temp = temp + dCurrent
            Wend
        End If
    Wend
    Dim primeNum As Long
    primeNum = 2
    i = 1
    While i <= max - 6
        i = i + 4
        If prime(i) = 1 Then primeNum = primeNum + 1
        i = i + 2
        If prime(i) = 1 Then primeNum = primeNum + 1
    Wend
    MsgBox "PrimeNum:" + Str(primeNum) + " Time:" + Str(GetTickCount - tt)
End Sub

计算到260万,340ms。