Fast Primes

[PhilOfPerth]

After some testing (which I personally found rather mind boggling), I've swapped over to a second version of this code which is even faster than what was above:

Code: (Select All)

Screen _NewImage(1280, 900, 32)

_Delay .5

_ScreenMove _Middle

For i = 1 To 999999 'I didn't stop at 1,000,000 just cause I didn't want that last SLEEP/CLS to erase the last page. Big Grin

    If IsPrime(i) Then Print i;

    If i Mod 10000 = 0 Then Sleep: Cls

Next

Beep 'an audible warning so folks can take their finger off whatever key they're using to spam past the SLEEP statements.

_Delay 2 'and time for them to let go of that key

_KeyClear 'so if they're using ENTER as the "Get on with it damn ya!" key, it won't blow past the manual test.

Print

Print



Print "Feel free to do some independent tesing to see if my response is speedy enough for you:"

Do

    Input "Give me a number from 0 to 1,016,064 and I'll tell you if it's prime or not.  (Zero quits.) =>"; num

    If IsPrime(num) Then

        Print num; "is, indeed, a prime number!"

    Else

        Print "Nope!"; num; "is not prime!"

    End If

Loop Until num = 0

System





Function IsPrime (num)

    'to check for any given number less than 1,016,064, we only have to do a maximum of 170 comparisons

    'as the max value we ever have to check against is the SQR of our number.

    'for example, no value higher than 10 could ever be a factor in 100 and be prime!

    'so for numbers less than 1,000,000, all we need do is compare them against factors less than 1,000.

    'and there's not that many of them, as you can see below!

    If num < 2 _Orelse num > 1016064 Then Exit Function

    Static As Long Prime_Array_Init, Prime_Factors(1 To 168), Factor_Count(1 To 10)

    Dim As Long factor_on, i, j, factor

    If Prime_Array_Init = 0 Then

        Prime_Array_Init = -1

        Restore Prime_Factor_Count

        For i = 1 To 10: Read Factor_Count(i): Next

        For i = 1 To 168: Read Prime_Factors(i): Next

    End If



    IsPrime = -1

    For j = 1 To 10 'broken down to give 10 quick exit points so we don't check every value for an answer.

        For i = 1 To Factor_Count(j)

            factor_on = factor_on + 1

            factor = Prime_Factors(factor_on)

            If num <= factor Then

                Exit Function

            Else

                If num Mod factor = 0 Then IsPrime = 0: Exit Function

            End If

        Next

        If num < factor * factor Then Exit Function

    Next



    Exit Function

    Prime_Factor_Count: 'each value here represents the number of prime factors in number increments of 100

    'for example, there are 25 prime numbers between 1 and 100, 21 primes between 101 and 200, ect...

    Data 25,21,16,16,17,14,16,14,15,14

    'and the actual prime factors go below here

    Data 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97: 'factors up to 10,000 (100 ^ 2)

    Data 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199: 'up to 44,100 (210 ^ 2)

    Data 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293: 'up to 93,636 (306 ^ 2)

    Data 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397: 'up to 160,000 (400 ^ 2)

    Data 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499: 'up to 252,004 (502 ^ 2)

    Data 503,509,521,523,541,547,557,563,569,571,577,587,593,599: 'up to 360,000 (600 ^ 2)

    Data 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691: 'up to 490,000 (700 ^ 2)

    Data 701,709,719,727,733,739,743,751,757,761,769,773,787,797: 'up to 652,864 (808 ^ 2)

    Data 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887: 'up to 820,836 (906 ^ 2)

    Data 907,911,919,929,937,941,947,953,967,971,977,983,991,997: 'up to 1,01,064 (1008 ^ 2)

End Function

The difference here is that we use an array to store these values, and look them up from the array, rather than restore and read them as direct DATA statements.

For quite some time now, I was always under the impression that arrays had a good bit of overhead to them, and that raw DATA was optimized and READ faster than array access was from the compiler.  Apparently that's not true, as array access is about 20 to 30 times faster than READ and DATA, from various tests I've been playing around with.  That just completely turns my expectations upside down!!

And thus, Steve the Amazing adapts and adjusts!!  If arrays are faster, so be it!  I now have an version which does Prime Numbers up to a little over 1,000,000, via using arrays to store the data. 

You've killed one of my dreams! For years now, I've been trying  (just as an exercise) to find a "formula" that lists all primes, with no success. 
Also had a go at finding PI, with the same result! Now I'll have to find another little conundrum to solve, to leave my mark in history!