Advertisement

# Primality Checker - Just Basic

Mar 5th, 2012
2,152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. REM Semi-Primitive Primality checker (checks N by dividing through all prime numbers from 2 to sqrt(N)
2. REM JB 1.1
3. REM by Ahmed Fatoum
4.
5. while (1) 'Infinite Loop
6. print 'new line
7. INPUT "Checking Primality from 2 till "; max 'input where to stop
8.
9. if max = int(max) and max >= 2 then ' if max is a whole number and larger than 2
10. approx = int(max/log(max)) ' approximation of needed space (wikipedia: prime number theorem)
11. amount = approx +  int(((2.04) ^ Log(max))) ' some heap bonus so we dont run out of memory space
12. PRINT "Let's count to max: ";max;", Approximate Amount: ";approx;"+";amount-approx
13. ' Code start
14.     DIM primes(amount) 'Reserve Memory space
15. ''''''''''''''''''''''''''''''''''''''''''' VARS
16.     primes(0) = 2 ' 2 is hard coded for easifying purposes
17.     pntr = 0 'pointer to last non-zero value
18.     alig = 6 ' how many primes each line?
19. ''''''''''''''''''''''''''''''''''''''''''' MAIN LOOP
20. start = time\$("ms") 'Start Stopwatch
21.
22.     for i = 2 to max 'Self-explainable
23.         for m = 0 to pntr 'from first recorded prime to last
24.             if (i mod primes(m) = 0 and i <> primes(pntr))  then 'break out of loop when 1 denominator is found
25.                 exit for
26.             else 'we can substitute sqr(i) for pntr but this way we save time (e.g: 308 sec saved from 1->100,000)
27.                 if primes(m) > sqr(i) then 'as stated above,for performance reasons we / through primes < sqr(number_to_check)
28.                     pntr = pntr+1 'increment pointer to pint to the newest prime number
29.                     primes(pntr) = i 'store a new prime
30.                         '''' OUTPUT START
31.                         If (x < alig-1) then
32.                             print primes(pntr), 'tabulator (horizontal space)
33.                             x = x + 1
34.                         else
35.                             print primes(pntr) 'line feed (newline)
36.                             x = 0
37.                         end if
38.                         '''' OUTPUT END
39.                     exit for 'we got our prime checked, checking till pntr is worth of time
40.                 end if
41.             end if
42.         next m 'check if we can divide it through next prime
43.     next i 'k, on to the next
44.
45. final = time\$("ms") 'End Stopwatch
46. print 'line feed
47. print "Array has been filled with ";pntr;"/(";approx;"+";amount-approx;") primes in "; final-start ;" ms." ' statistics
48. else
49. if max = 0 then end
50. PRINT "please use a natural number >= 2"
51. end if
52. WEND
53. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement