Thuật giải đếm số nguyên tố

[LPS86]

Em muốn đến các số nguyên tố từ 1 đến 100.000.000
Thuật giải của em như sau :

            int so=1;
            bool co=true;
            for(int i = 2 ; i<100000000 ; i++)
            {
                for(int j=2;j<Math.Sqrt(i)+1;j++)
                {
                    if (i % j == 0)
                    {
                        co = false;
                        break;
                    }
                    else co = true;
                }
                if (co)
                {
                    so++;
                }
            }

Tuy nhiên với thuật giải này nó chạy quá lâu .Nghe nói trong C# còn 1 thuật giải khác để đếm (hoặc in ra) số nguyên tố hiệu quả hơn nhiều lần ! Ai biết có thể cho em tham khảo được không ạ ?

[nhc1987]

Nếu chạy với số lượng lớn như vậy thì nên code multi thread . Có thể refine đoạn code trên giúp chạy nhanh hơn "tí xíu" còn thuật toán hiệu quả hơn thì ko biết có hay ko .

[BuithiHa]

bạn nên thêm hay dòng code sau ở phía trên khi tìm số nguyên tố(không phải tìm 1 dãy như trên mà tìm một số bất kì

if(n<2) return 0;//false
	if(n==2) return 1;//true

[Haipt]

Em muốn đến các số nguyên tố từ 1 đến 100.000.000
Thuật giải của em như sau :

            int so=1;
            bool co=true;
            for(int i = 2 ; i<100000000 ; i++)
            {
                for(int j=2;j<Math.Sqrt(i)+1;j++)
                {
                    if (i % j == 0)
                    {
                        co = false;
                        break;
                    }
                    else co = true;
                }
                if (co)
                {
                    so++;
                }
            }

Tuy nhiên với thuật giải này nó chạy quá lâu .Nghe nói trong C# còn 1 thuật giải khác để đếm (hoặc in ra) số nguyên tố hiệu quả hơn nhiều lần ! Ai biết có thể cho em tham khảo được không ạ ?

Nếu hiểu rõ hơn chút bạn sẽ giảm được 70% vòng lặp, đương nhiên tăng tốc độ lên 300%
+ Các số chẵn > 2 không thể là các số nguyên tố( để bước lặp ++ 2, bỏ qua tất cả các số chẵn )
+ Các số chia hết cho 3,5,7 không thể là số nguyên tô( ngoại trừ 3,5,7)

[LPS86]

Nếu hiểu rõ hơn chút bạn sẽ giảm được 70% vòng lặp, đương nhiên tăng tốc độ lên 300%
+ Các số chẵn > 2 không thể là các số nguyên tố( để bước lặp ++ 2, bỏ qua tất cả các số chẵn )
+ Các số chia hết cho 3,5,7 không thể là số nguyên tô( ngoại trừ 3,5,7)

Hix code trên là em viết đơn giản ra để mà mọi người hiểu rõ về thuật toán của em thôi *_*Chứ trong bài dĩ nhiên là em phải có chỉnh sửa cho nhanh hơn chút xíu .Tuy nhiên vẫn quá chậm .Xử lí đến 100tr mất 10ph lận ,trong khi đề ra là 1 ph *_*
Theo Training thì cho vào 1 cái mảng .Sau dó chia các số của mảng cho số ở vị trí thứ nhất (bắt đầu từ số 2). Các số chia hết cho số bé nhất thì bị loại ra khỏi mảng *_* Tức là sau khi làm 100tr phép chia ta còn lại 50 tr số lẻ .Tiếp đó chia cho vị trí thứ 2 của mảng là số 3.Tức là làm 50tr phép tính nữa .Ta sẽ còn lại 33,33 tr số .Tiếp tục chia cho vị trí thứ 3 là số 5 (vì số 4 đã bị loại khỏi mảng do chia hết cho 2).Tức là làm tiếp 33,33 tr phép tính nữa ta sẽ còn 23,33tr số..... Cứ như vậy cho đến khi số tại index > 10.000(căn 2 của 100tr) thì ngưng và in mảng ra *_*
Lí thuyết là thế và ông thầy cũng biểu diễn ,nó chạy có chưa đến 10s *_*Nhưng em không biết biến nó thành thuật toán thế nào ! Mong các bác giúp đỡ

Về chuyện bước lặp +2 như bạn nói thì thực ra cũng chỉ bớt được 3*50tr = 150tr phép tính(mỗi số chẵn cần 3 phép tính là loại được rồi).Chia hết cho 3,5,7 cũng không mất nhiều thơi gian đâu *_* Cái làm mất nhiều thời gian nhất là các số nguyên tố kìa .