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

我也想知道

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

举几个例子吧:

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

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

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

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

有办法减少开方的运行时间吗？
很多关于求素数的算法，都要用到开方，只要求精确到整数部分即刻。
有谁能写这样的函数吗？
当然写出的函数不能比自带的函数更慢。

没有数学基础是不行滴

我也就只理解到了
i = 2 To Sqr(n)这句了，
另外，我觉得如果不用＃define，程序执行速度还能快那么一点点，一点点，呵呵。

To menglv:
基本上很难在开方上更快了,拿VC来说,它几乎是把sqrt()直接转成了机器指令fsqrt,就是说开方和一个普通的浮点数加减法速度差别不会很大.

To 冬瓜汤:
define是预编译指令,在编译之前已经就展开了,它不是定义变量,不会影响运行速度,可能会影响一点点编译花的时间.

25楼的源程序，不用开方的。
我实在没办法再进一步优化了。
如果算到1001990，仅需282毫秒！！！
附件:ssh.rar

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

可以不用开方的

循环条件就是while(i*i < n)啦  一个整数乘法而已

gooooooooood

haoooooooooooooooo

大数运算？？？？？？

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

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

记得要跳过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。

DDDDDD

真是高手云集啊    长了见识

开根号的话速度肯定是快的。因位如果判断一个数字n是否是素数，只需要计算sqrt(n)-1步就够了。我也写个C的吧。计算2-10000内的素数只需40毫秒

#include <stdio.h>
#include <math.h>
#include <time.h>

void main()
{
        int n,s,m,nb,max;
        clock_t start, end;
        nb=0;
        max=10000;
                start=clock();
                for(n=2;n<=max;n++){
                        s=1;
                        for(m=2;m<=sqrt(n);m++){
                                    if(n%m==0)s=0;
                        }
                        if(s==1)
                        {nb++;}
                }
                end=clock();
                printf("2-%d内共有%d个素数\n",max,nb);
                printf("时间:%f毫秒\n",(double)(end-start));
}

个人觉得，这已经够快的了，去掉偶数的判断最好不要，因为，计算机在循环处理判断后的总时间反而会慢。

汗，头一次被人说翻老帖……
我用的也是筛法，1000万以内670ms左右，把那个多余的循环去掉640ms左右，100万以内60ms左右，1万的话不到1ms。代码可以再优化，不过我比较懒……
我的CPU是 P4 1.6GHz，单纯说时间一点意义都没有，不同的配置，不同的使用情况，时间肯定有差异，研究算法的一般是用算法分析，研究研究最坏和平均情况什么的。
另外，要想速度快，不但算法要合适，还得注意优化，乘法除法取模不要用得那么频繁，更不用说sqrt了，输出最好别太分散，更多的策略和技巧，我就不会了……
顺便问问，调试区怎么出了个算法帖？

#include <windows.h>
#include <math.h>

#define PRIME 0
#define COMPOSITE 1

#define MAX_COUNT 10000000L

int
WINAPI
WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    DWORD start = GetTickCount();
    // begin
    char * prime = new char [MAX_COUNT+1];
    prime[2] = PRIME;
    int n, m, s, q;
    for( n = 4; n <= MAX_COUNT; n += 2 )
    {
        prime[n] = COMPOSITE;
    }
    // the next for loop is not always necessary
    for( n = 3; n <= MAX_COUNT; n += 2 )
    {
        prime[n] = PRIME;
    }
    q = (int)sqrt((float)MAX_COUNT);
    for( n = 3; n <= q; n += 2 )
    {
        if( prime[n] == PRIME )
        {
            for( m = n*n, s = n+n; m<= MAX_COUNT; m+= s )
            {
                prime[m] = COMPOSITE;
            }
        }
    }
    // end
    DWORD end = GetTickCount();

    // output routine goes here

    delete prime;
}