Advertisement
a3f

Primality Checker - Just Basic

a3f
Mar 5th, 2012
3,209
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