Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- REM Semi-Primitive Primality checker (checks N by dividing through all prime numbers from 2 to sqrt(N)
- REM JB 1.1
- REM by Ahmed Fatoum
- while (1) 'Infinite Loop
- print 'new line
- INPUT "Checking Primality from 2 till "; max 'input where to stop
- if max = int(max) and max >= 2 then ' if max is a whole number and larger than 2
- approx = int(max/log(max)) ' approximation of needed space (wikipedia: prime number theorem)
- amount = approx + int(((2.04) ^ Log(max))) ' some heap bonus so we dont run out of memory space
- PRINT "Let's count to max: ";max;", Approximate Amount: ";approx;"+";amount-approx
- ' Code start
- DIM primes(amount) 'Reserve Memory space
- ''''''''''''''''''''''''''''''''''''''''''' VARS
- primes(0) = 2 ' 2 is hard coded for easifying purposes
- pntr = 0 'pointer to last non-zero value
- alig = 6 ' how many primes each line?
- ''''''''''''''''''''''''''''''''''''''''''' MAIN LOOP
- start = time$("ms") 'Start Stopwatch
- for i = 2 to max 'Self-explainable
- for m = 0 to pntr 'from first recorded prime to last
- if (i mod primes(m) = 0 and i <> primes(pntr)) then 'break out of loop when 1 denominator is found
- exit for
- else 'we can substitute sqr(i) for pntr but this way we save time (e.g: 308 sec saved from 1->100,000)
- if primes(m) > sqr(i) then 'as stated above,for performance reasons we / through primes < sqr(number_to_check)
- pntr = pntr+1 'increment pointer to pint to the newest prime number
- primes(pntr) = i 'store a new prime
- '''' OUTPUT START
- If (x < alig-1) then
- print primes(pntr), 'tabulator (horizontal space)
- x = x + 1
- else
- print primes(pntr) 'line feed (newline)
- x = 0
- end if
- '''' OUTPUT END
- exit for 'we got our prime checked, checking till pntr is worth of time
- end if
- end if
- next m 'check if we can divide it through next prime
- next i 'k, on to the next
- final = time$("ms") 'End Stopwatch
- print 'line feed
- print "Array has been filled with ";pntr;"/(";approx;"+";amount-approx;") primes in "; final-start ;" ms." ' statistics
- else
- if max = 0 then end
- PRINT "please use a natural number >= 2"
- end if
- WEND
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement