有没有更快的方法来查找素数。 [英] Is there a faster way to find prime numbers.

问题描述

我花了大约40秒才能通过100000.

我因为花了这么长时间才杀死了100万。

我正在运行运行@ 4.5Ghz的FX6100并且仅使用15％。

我已经考虑过运行多个线程并对它进行了一些研究

但我从未这样做过。我只是想知道是否有任何建议使这个代码更有效。



提前致谢。 :)

It takes me about 40 seconds to go through 100000.
I killed to process for 1 million because it was taking so long.
I'm running a FX6100 running @ 4.5Ghz and only using 15%.
I have thought about running multiple threads and done just a wee bit of research on it
but I have never done that. I'm just wondering if there are any suggestions for making this code more efficient.

Thanks in advance. :)

Private Sub btnGo_Click(sender As Object, e As EventArgs) Handles btnGo.Click
      Dim j As Integer = 1
      Dim c As Integer
      Dim max As Integer = 100000
      For I As Integer = 1 To max
          j = I
          c = 0
          Do
              If I Mod j = 0 Then
                  c += 1
                  If c > 2 Then
                      Exit Do
                  End If
              End If
                  j -= 1
          Loop Until j = 0
          If c = 2 Then
              lbxSquare.Items.Add(I.ToString())
          End If
          If I = max Then
              lbxSquare.Items.Add("There are " & lbxSquare.Items.Count.ToString() & " prime numbers")
          End If
      Next
  End Sub

推荐答案

最好的方法是使用查找素数 [ ^ ]。

The best way is to use the Sieve of Eratosthenes as described in Finding prime numbers[^].

这是一个用C＃编写的解决方案。

查找所有素数高达100000所需的时间不到20毫秒。大约需要5秒才能找到高达10百万的素数。

我的电脑是AMD FX6100 @ 3.3G。

Here is a solution written in C#.
It takes less than 20 milliseconds to find all the prime numbers up to 100000. About 5 seconds to find all up to 10 millions.
My PC is an AMD FX6100 @ 3.3G.

private static void Main(string[] args)
{
    var sw = Stopwatch.StartNew();
    var collection = new List<int>();

    //assume "2" as known, so let's start from 3
    for (int i = 3; i < 100000; i += 2)
    {
        //no reason to scan over the square-root of the integer under test
        double root = Math.Sqrt(i);

        bool found = false;
        for (int k = 0, count = collection.Count; k < count; k++)
        {
            int divisor;
            if ((divisor = collection[k]) > root)
            {
                //no futher reason to scan
                break;
            }
            else if ((i % divisor) == 0)
            {
                //found a divisor
                found = true;
                break;
            }
        }

        if (found == false)
        {
            //no divisor found, so add yet another prime number!
            collection.Add(i);
        }
    }

    //insert the known "2" as the very first
    collection.Insert(0, 2);

    Console.WriteLine("time=" + sw.ElapsedMilliseconds);
    Console.WriteLine("count=" + collection.Count);

    //display the entire collection (a text file on disk would be better, though)
    //foreach (int num in collection)
    //{
    //    Console.Write("{0}; ",num);
    //}

    //wait for a user keypress
    Console.ReadKey();
}

尝试以下逻辑..

try below logic..

Dim p, n, i As Integer
p = 1
Print "Prime Numbers are : "
For n = 1 To 100
For i = 2 To n – 1
If n Mod i = 0 Then
p = 0
Exit For
Else
p = 1
End If

Next
If p = 1 Then
Print n
End If

Next

这篇关于有没有更快的方法来查找素数。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！