A Prime Number Question

[Code Doc]

I hate to date myself, but it seems that when I first learned algebra, a prime number was defined as "an integer that can only be divided evenly by itself and 1."

Now it appears that 1 has been excluded from the set of all prime numbers because a prime number is "an integer that can be obtained only by multiplying two different integers, itself and 1." Because 1 is not different from 1, 1 is thus not a prime number.

Does anyone know when 1 was excluded formally from the set of all prime numbers and what the reason was for doing it?

[Logophobic]

Wikipedia

[Code Doc]

Wikipedia

Thanks, Logophobic. Apparently there are a few die hard mathematicians who still believe that 1 is a prime number, but their numbers are dwindling.

I like this quote: "God may not play dice with the universe, but something strange is going on with the prime numbers."

I personally have written some brute force VB6 code that will find the first 1,000 primes rather rapidly. However, I'm too embarrassed to post it. One of my colleagues wrote code that would find the first 10,000 primes faster than my feeble program would fiind the first 1,000.

[MaximilianMayrhofer]

It would be interesting to see your colleagues code, as it might be possible to modify it for other mathematical functions

[Code Doc]

It would be interesting to see your colleagues code, as it might be possible to modify it for other mathematical functions

This runs faster than his does (my revised VB6 code). On my machine (1.7 Ghz), I can find the first 20,000 primes and throw them into a list box in less than 10 seconds:

Dim MyNumber As Long, NumFactors As Integer

Private Sub Form_Load()
MyNumber = 1
Do While List1.ListCount < 20000
    NumFactors = 0
    MyNumber = MyNumber + 1
    For I = 1 To Sqr(MyNumber)
        If MyNumber / I = MyNumber \ I Then
            NumFactors = NumFactors + 1
            If NumFactors > 1 Then Exit For ' Not a prime
        End If
    Next
    If NumFactors = 1 Then List1.AddItem Str$(MyNumber) ' Prime Found
Loop
End Sub

If this program runs correctly, the 20,000th prime number is 224,737. The sequence starts with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

[Logophobic]

This code is a more optimized version of the method you used. If you scroll down a bit on the Wikipedia page I linked to, you'll find a second titled "Pseudocode for programs to find primes". Note that this code is precisely what is described therein as the "least efficient algorithm", except that it only checks against primes up to the square root of the candidate. Also note that it takes a lot longer to populate the listbox than it does to find the primes.

  Dim MyNumber As Long
  Dim Root As Long
  Dim Prime(19999) As Long
  Dim Count As Long
  Dim I As Long
  
  MyNumber = 2
  Prime(0) = 2
  Count = 1
  Do While Count < 20000
    MyNumber = MyNumber + 1
    Root = Int(Sqr(MyNumber))
    I = 0
    Do Until Prime(I) > Root
      If MyNumber Mod Prime(I) = 0 Then Exit Do
      I = I + 1
    Loop
    If Prime(I) > Root Then
      Prime(Count) = MyNumber
      Count = Count + 1
    End If
  Loop
  
  List1.Clear
  For I = 0 To 19999
    List1.AddItem CStr(Prime(I))
  Next I

[TTn]

Prime numbers are pretty cool.

Here is my distributed project to discover large prime numbers:
http://groups.myspace.com/My15k
Written with VB.NET 2005.
It's surely the fastest project method around for the last couple years.
I need more members to join the project, to validate this claim.
GIMPS (the leading project) uses a brute force method with many PC's.
The Mersenne algorithm is only slightly faster than the LLR(Lucas-Lehmer-Riesel) algorithm,
and Mersenne primes are getting more and more sparce because of the form of the prime being tested.
The LLR algorithm has many primes in an obtainable range, so the gaps dont cause large gaps in the newer discoveries. We just need more pc's!

[Code Doc]

This code is a more optimized version of the method you used. If you scroll down a bit on the Wikipedia page I linked to, you'll find a second titled "Pseudocode for programs to find primes". Note that this code is precisely what is described therein as the "least efficient algorithm", except that it only checks against primes up to the square root of the candidate. Also note that it takes a lot longer to populate the listbox than it does to find the primes.

Logophopic, I am not sure the code you posted is an improvement over mine for several reasons, the most important being that the primes are being stored in an array which will become an enormous memory hog when the number of primes found becomes huge.

My code can be altered slightly by just dumping the primes into a file (rather than a list box) as they are found for later retrieval. Thus, there is almost no limit to how many can be found, especially if the data type for MyNumber, Long, is changed to Double. The capacity of the hard drive would set the limit if the intention is to store them all. I used the list box to show the results only for demonstration.

Eventually, Sqr(MyNumber) becomes a controlling factor to the CPU time when it becomes huge, and that is perhaps the principal reason why my code is "brute force"--very fast initially but slow when enormous primes are eventually encountered.

If our objective is not to store them all but in fact to find the largest possible prime within the limits of double precision (~10^308), that proposes an interesting alternative. We could track the time intervals required to find the last hundred of the first 20,000 primes and use that as a sample for predicting the CPU time required to find the largest prime within the limits of double precision. I imagine its a non-linear function but well within the capabilities of curvilinear regression and the necessary extrapolation.

[TTn]

Eventually, Sqr(MyNumber) becomes a controlling factor to the CPU time when it becomes huge, and that is perhaps the principal reason why my code is "brute force"--very fast initially but slow when enormous primes are eventually encountered.

Hey that's funny that "brute force" kind of applies in your situation too, but not really for the same reason I was talking about.
They have many members, so the brute force of popularity alone has lead to their huge discoveries.
Its the form of a Mersenne prime, and it's prime exponent, that leads to the increasing gaps, although for the same reason the individual test is the fastest known, and attracts new members to join.
So the form of Mp drops off after a certain point, where in your case you've already included all of them in the densest form possible.
It's the limitation of the computation that slows you down.
The LLR algorithm has the best of both worlds, combining a fast test with a much denser form than Mp.
It's also fun to discover the largest prime numbers known!

[Merri]

We had this contest about prime numbers... I had a very fast finding algorithm, but I lost because I didn't optimize adding to listbox (which was, silly enough, counted into the benchmark). Later on NoteMe tested only the algorithms and found mine to be the fastest

My contest entry code

I don't have VB on this machine, otherwise I'd get the actual code out of there. The code is not fit for finding insanely large prime numbers.

[Logophobic]

Code Doc, your code divides the number by all integers up to its square root, including composite numbers which cannot be factors of the number. The code I provided is an improvement to yours because it avoids this unecessary division. In order to do that, we need to access a list of prime numbers, which is exactly what the program creates. As for memory usage, 1 MB is enough to store the first 262,144 prime numbers as Long. The last of these is 3,681,131, making this small amount of memory sufficient to find all primes up to about 1.355E+13.

[Code Doc]

Code Doc, your code divides the number by all integers up to its square root, including composite numbers which cannot be factors of the number. The code I provided is an improvement to yours because it avoids this unecessary division. In order to do that, we need to access a list of prime numbers, which is exactly what the program creates. As for memory usage, 1 MB is enough to store the first 262,144 prime numbers as Long. The last of these is 3,681,131, making this small amount of memory sufficient to find all primes up to about 1.355E+13.

Agreed. And, I believe you do recognize that memory does become significant when the primes get to be huge. I am a bit surprised you did not see my point about letting the clock tick on and on to find the largest possible prime within the limits of double precision.

Granted, my code makes no effort to analyze previous primes already found in an effort to speed execution. I imagine that ignoring composites in the division also speeds the search, assuming the division process is significantly slower than the check. But it appears my code also misses no primes at all enroute to finding larger ones, and memory is not an issue. Also, we can revise it to start at any point in the prime number sequence to find the next larger one (set MyNumber = 10^15 or so. The theory is that there is really no limit to the the size of a prime number and that the largest one has yet to be found.

What I would like to see is an estimate of the time required to find a prime number that reaches the top end of double precision (10^308), using an extrapolation based on the time that a 2 GHz+ Pentium PC takes to find 100 relatively large ones. To me, that would be rather interesting because at least you would know in advance approximately how long the machine would have to crank. If it has to run for several months or so, then the exercise, of course, is useless.

[TTn]

Okay I'll let you two play in the sandbox.