display | more...
A Casio program project started in the fall of 2000, and not completed until late spring 2001. The project was to make a Casio program capable of telling prime numbers apart from ordinary numbers. We knew it already excisted, as it came with the calculator, but we still wanted to figure out how to do it. My team consisted of myself, and two other creme de la creme Casio programmers; Codepie, and Teh Confuz0r (1337 factor 12).

The theory behind telling a prime number from an ordinary number in a simple Basic program with limited functions, was cracked out as joint venture between the three of us, and is as follows:

Everybody knows that prime numbers can only be divided by 1 and itself. So what we needed to do was to try to divide the number in question with all the integer values between 2 and the value that was the number itself divided by 2. Why "the value that was the number itself divided by 2"? It isn't necessary but it cuts the computing time in half when the number in question really is a prime number. Let me demonstrate why:
No higher values of the divisor will render a number that is =>2, thus it is not necessary to do these calculations.
All this was easy, the problems came when we had to find out if the quotient had any decimals in it. This is done by multiplying the integer value of the quotient with the divisor. If the product equals the dividend, the quotient has no decimals in it.
So if a given number is divided by all integer values between 2 and half of the number in question, and all of the calculations show up having decimals, we know that the number is prime. And if one or more of the calculations show up without decimals, the number is not prime, logically enough :)
So far we are still in the autumn, 2000. It was when we where ready to move off the paper, and onto the 64KB monster of a machine, that new problems arrived. We could not find a way to change between systems of notation mid-program. We needed to go from normal (Floating point), to integer, and back to normal, for each calculation. The answer didn't present itself until the spring of 2001. During a German class, I was goofing around, and found a very simple function allowing one to define what system of notation to use. In retrospect I realize that I could just have used a similar function to extract the values behind the comma, and check if it was larger than 0. Well, well...

On to the source already:
(Compatible with the 9X50 range of Casio calculators, maybe others aswell.)
All text not within "" are functions, and should not be typed, rather than found within some submenu.
All lines end with a "next-line-bent-arrow-thingie" (Looks like your return button.), except for those that end with a ». In place of these should a "stop-and-wait-for-exe-thingie" be put. (Looks like a triangle pointing down, and to the right)
-> is the "save as" button.

Lbl 1
Lbl 2
If B>A÷2
Then "IS PRIME:"
"1 AND SELF" »
Goto 1
If Intg C×B=A
Then B->D
D »
Goto 1
Else Isz B
Goto 2

Of course all text is editable. My observations show that this program is far more optimized than the one that comes with the calculator.

Further optimizations :

RolloThomasi's algorithm works by stopping when it finds the smallest prime-factor of A or when it is sure that A is prime. For example, with 1,573,499 (23 × 37 × 43²), it only needs to check until it reaches the smallest prime-factor, which is 23. When is the earliest we can stop checking for prime factors of A, because we are sure that A is prime ? We need to figure out how big the smallest prime-factor (f1) can possibly get.

A non-prime number is equal to all its prime factors multiplied together :

  • A = f1 × f2 × … × fn
So, using algebra, we know the smallest prime-factor of A is :
  • f1 × f2 × … × fn = A (same as above, only reversed)
  • f1 = A ⁄ (f2 × … × fn)
So, to figure out what the maximum possible value of f1 is, we need to figure out what the minimum possible value of (f2 × … × fn) is. The minimum possible value of (f2 × … × fn) happens when A has only two equal prime-factors. For example, 169 has only two equal prime factors (13 and 13). So, we use the following algebra :
  • f1 = A ⁄ f2
  • f1 = A ⁄ f1 (since f1 = f2)
  • f1² = A
  • f1 = √A
And, we see that the highest we ever have to check is the square root of A, which is almost always lower than half of A (which is how high RolloThomasi's program will check). Also, think about what happens when f2 is greater than f1 and about what happens when you add in more prime factors; you should find that the highest you have to check actually goes lower than the square root of A, so by checking up to the square root of A, you'd be doing all you need to and then some.

You can also further speed things up by eliminating floating-point numbers; if the square root has anything after the decimal point, you can ignore it. If we are checking whether 211 is prime, √211 ≈ 14.526, so we only need to check up to 14.

You can also skip checking against all even numbers, except for two. If the number wasn't divisible by two, it won't be divisible by any other even number. This is fairly easy to do by adding two to B each cycle instead of one (don't forget to check numbers by dividing by two).1

To further enhance the skipping optimization, you can check against only two, three, and all numbers that fit the forms of 6k − 1 and 6k + 1 to further reduce the number of factors to check.

1What I have covered so far can be found in C at the Useful Number Theory functions in C node.

Years ago I wrote my own prime number generator in QBasic. Using only 10 lines of code, it was as efficient as I considered possible. (Correct me if I'm wrong. I didn't have a lot of experience back at the time, and a lot of my BASIC knowledge has faded through the ages.)

10 OPEN "prime.txt" FOR APPEND AS #1
20 PRINT #1, " 2": PRINT , " 2"
30 FOR A& = 3 TO 2147483647 STEP 2
40 FOR X& = 3 TO INT(SQR(A&)) STEP 2
50 Y# = A& / X&
60 IF Y# = INT(Y#) GOTO 90
70 NEXT X&
80 PRINT #1, A&: PRINT , A&
90 NEXT A&
100 END

10: Creates a file called PRIME.TXT to which the prime numbers will be appended.

20: 2 is hard-coded because it is the only even prime. Only checking odd numbers doubles the processing speed. (See line 80 for the explanation of the preceding blank space.)

30: A FOR loop that runs through all odd numbers between 3 (the smallest candidate prime greater than 2) and 2,147,483,647 (the maximum value of a long integer in QBasic).

40: A nested FOR loop that runs through all candidate proper divisors of A&. There's no use searching for divisors greater than the square root, since they can't possibly be integers. As Olathe already pointed out, the integer part of this square root is what you really need for this. At first I absent-mindedly forgot the STEP 2. Since I don't run through even numbers, they can't have even divisors. Eliminating this inefficiency doubled my processing speed again.

50: Assigns the quotient A&/X& to a double precision number. I haven't tested if single precision would produce any false primes, but I just wanted to be safe.

60: If a proper divisor of A& is found, it isn't a prime number. This is done by casting Y# to an INT and comparing it with Y# itself. If they are equal (i.e., Y# has nothing after the decimal point), X& is a proper divisor. The program breaks the nested loop and continues with the next candidate prime.

70: As long as no proper divisor is found, the program patiently tries the next X&.

80: If the nested loop ends without finding a proper divisor (line 60), A& is appended to #1 (the file created on line 10) and printed on the screen. We have found a prime number! For some reason, a blank space precedes the numbers in the file and a tab those on screen. I have no idea why this is, but I'm only interested in functional code, so I didn't waste time and code on the layout.

90: The program checks the next candidate, regardless of the previous result.

100: Ends the program and closes the file.

Although I only had a 80386 at the time, I was very satisfied with the speed it spew results. I checked the first scores of results against an existing table to assure the faultlessness of my program, and of course I checked whether it had recognized 31337. =)

If you think this code is of any use, feel free to borrow it. Supposedly we may assume the program works accurate, but the full responsibility for any inconvenience/damage/financial loss whatsoever lies entirely with the person using the code. I provide it as is without any warranty.

Log in or register to write something here or to contact authors.