Prime number test / factorization

Contributions to this software library are always welcome. Please ensure that you post program listings rather than .raw files. They give a reasonable idea of what your program does without having to load them into a DM42 and you can also include comments in your code. Check out the following link for a decoder/encoder: https://technical.swissmicros.com/decoders/dm42/

You can then copy/paste the listing and post it in "code" tags.
Post Reply
User avatar
rudi
Posts: 415
Joined: Wed Nov 03, 2021 9:03 am
Location: Denmark
Contact:

Prime number test / factorization

Post by rudi »

I made a small program, 142 bytes, that can test if a number is a prime number.
The program uses no registers or variables, but the entiere stack is used.

To use the program, enter the number to be tested in x and XEQ "PRIME".

Example, test 117747:
Image

117747 is not a prime, it is divisible by 3
Image


Another test, is 98765201 a prime:
Image

The rarely seen seagul is flying for a couple of seconds...
Image

... and the program announces that 98765201 is indeed a prime:
Image

The program can easily be used to find all primefactors for a number, by repeatedly calling the program, press the divide key until a prime is reached. See comments in the program listing below.

One of the max prime numbers that can be tested with this program, 99 999 999 977, takes 2 minutes and 22 seconds on batteries and 57 seconds running on USB power. I tried disabling the screen update with RefLCD, but it didn't reduce the execution time significantly.

The program spends 7 minutes and 37 seconds on batteries to confirm that 999 999 999 989 is a prime number.
Last edited by rudi on Fri Jun 17, 2022 8:43 am, edited 2 times in total.
/Rudi

DM-42 (s/n 06999), HP-42S, HP-35s, HP-11c, HP-32SII (ex HP-41CV, ex HP-75C, ex HP-48G + a lot, really lot of a accessories)
Denmark
User avatar
rudi
Posts: 415
Joined: Wed Nov 03, 2021 9:03 am
Location: Denmark
Contact:

Re: Prime number test / factorization

Post by rudi »

There's a bug in the upper limit test in the version in the first post, I'll fix that and upload a new version later.

Edit 18:45
Here's the new modified version, with upper limit sanity check.

Code: Select all

00 { 144-Byte Prgm }
@  
@   PRIME number check by Rudi Bjørn Rasmussen
@   Use no registers or variables, but the entiere stack.
@ 
@   Usage:
@   Enter the number to test in x and run "PRIME".
@   A message will either show "PRIME" or "NOT PRIME"
@   when the program has finished.
@   The y register will contain the number that is being
@   tested and the x register the "next" factor that divides
@   the number being tested. If the number is a prime, 
@   then both x and y will show the number being tested.
@ 
@   Example:
@   x: 117747
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   y: 117747
@   x: 3
@ 
@   117747 is not a prime, it can be divided by 3
@ 
@   The program can also be used to find all prime factors for a number:
@   x: 117747
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   y: 117747
@   x: 3
@   press the divide key [/] to test next factor
@   x: 39249
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   y: 39249
@   x: 3
@   press the divide key [/] to test next factor
@   x: 39249
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   y: 13083
@   x: 3
@   press the divide key [/] to test next factor
@   x: 4361
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   x: 7
@   press the divide key [/] to test next factor
@   x: 623
@   EXQ "PRIME"
@   ... =>
@   "NOT PRIME"
@   x: 7
@   press the divide key [/] to test next factor
@   x: 89
@   EXQ "PRIME"
@   ... =>
@   "PRIME"
@   y: 89
@   x: 89
@   Done, thus 117747 = 3 * 3 * 3 * 7 * 7 * 89
@ 
01▸LBL "PRIME"
02 XEQ 04 @ validate input
03 ENTER
04 SQRT @ check limit
05 IP
06 X<>Y
07 2 @ 2 is per definition a prime number
08 X=Y?
09 GTO 06 @ if 2, then finish
10 XEQ 00 @ check if an even number
11 1
12 + @ 3 is the first uneven number to check with
13▸LBL 03 @ main loop
14 XEQ 00 @ check current factor
15 2
16 + @ next factor
17 GTO 03 @ continue looping
18▸LBL 00 @ factor check
19 RCL ST Y
20 X<>Y
21 MOD
22 X=0? @ is number dividable with factor?
23 GTO 01 @ then finish, not a prime
24 R↓
25 LASTX
26 R^
27 X<Y? @ have we reached the checking limit?
28 GTO 02 @ yes - no factors found, this is a prime, finish
29 R↓
30 RTN @ limit not reached, continue checking
31▸LBL 01 @ the input is not a prime
32 STO ST T
33 STO ST Z
34 R↓
35 LASTX
36 "NOT PRIME"
37 AVIEW
38 STOP @ show message and stop
39▸LBL 06 @ check number was 2, special handling
40 ENTER @ duplicate and fall through
41▸LBL 02 @ end of check reached, the number is a prime
42 0
43 STO ST Z
44 STO ST Y
45 R^
46 ENTER
47 "PRIME"
48 AVIEW
49 STOP @ show message and stop
50▸LBL 04 @validate input
51 0
52 X<>Y
53 +
54 X=0? @ input can not be zero
55 GTO 05
56 X<0? @ input can not be negative
57 GTO 05
58 FP @ input must be an integer
59 X≠0?
60 GTO 05
61 LASTX
62 999999999999 @ input can not exceed maximum integer number
63 X<Y?
64 GTO 05
65 CLST
66 LASTX
67 RTN
68▸LBL 05 @ show invalid input message
69 CLST
70 LASTX
71 "INVALID INPUT"
72 AVIEW
73 STOP
74 END
Attachments
PRIME.raw
(147 Bytes) Downloaded 140 times
/Rudi

DM-42 (s/n 06999), HP-42S, HP-35s, HP-11c, HP-32SII (ex HP-41CV, ex HP-75C, ex HP-48G + a lot, really lot of a accessories)
Denmark
Post Reply