I've made a short program that tests for primality. The user enters a number, and if the number isn't prime, it lists its factors; if it is prime, it says so. This is my first TI program, actually; I made it a few days ago.
Once it gets into the archive, hopefully it'll be useful. I'm sure there are other prime testing programs out there, though.
UPDATE: It's been rejected for the archive. I may not have uploaded it as a .zip.
What algorithm do you use to check for primality?
Are you using a probabilistic test like Miller–Rabin or are you doing some variant of brute-force checking?
mr womp womp wrote:
What algorithm do you use to check for primality?
Are you using a probabilistic test like Miller–Rabin or are you doing some variant of brute-force checking?
Brute force. It loops through all the hypothetical factors from 2 to n-1. If iPart(n/factor)=n/factor, factor goes into n evenly and is printed. It could be made to run a lot more quickly, for example by stopping the for loop at n/2. I will implement that soon, probably.
Nice work
You may be interested in this pseudo code used for fast prime factor lookup:
Code: input n
while remainder(n, 2) is 0
{
primes[total_primes] = 2
total_primes = total_primes + 1
n = n / 2
}
if n is 1 return
div = 3
end = sqrt(n)
while 'div' less than or equal to 'end'
{
if remainder(n, div) is 0
{
do
{
primes[total_primes] = div
total_primes = total_primes + 1
n = n / div
} while remainder(n, div) is 0
if n is 1 return
end = sqrt(n)
}
div = div + 2
}
primes[total_primes] = n
total_primes = total_primes + 1
MateoConLechuga wrote:
Nice work
You may be interested in this pseudo code used for fast prime factor lookup:
Code: input n
while remainder(n, 2) is 0
{
primes[total_primes] = 2
total_primes = total_primes + 1
n = n / 2
}
if n is 1 return
div = 3
end = sqrt(n)
while 'div' less than or equal to 'end'
{
if remainder(n, div) is 0
{
do
{
primes[total_primes] = div
total_primes = total_primes + 1
n = n / div
} while remainder(n, div) is 0
if n is 1 return
end = sqrt(n)
}
div = div + 2
}
primes[total_primes] = n
total_primes = total_primes + 1
Thank you!
I think I can tell somewhat how the lines after div = 3 work, but I'm having trouble understanding what this part is for, especially since total_primes isn't defined earlier in the program:
Code:
input n
while remainder(n, 2) is 0
{
primes[total_primes] = 2
total_primes = total_primes + 1
n = n / 2
}
Could you help me understand it?
It simply keeps dividing the number by 2. total_primes starts at 0.
![[t]](/forum/templates/Cemetech6/images/twitter.png)
![[f]](/forum/templates/Cemetech6/images/fb.png)
![[RSS]](/forum/templates/Cemetech6/images/rss.png)