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.

Register to Join the Conversation

Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»

Go to Registration page

You **cannot** post new topics in this forum

You **cannot** reply to topics in this forum

You **cannot** edit your posts in this forum

You **cannot** delete your posts in this forum

You **cannot** vote in polls in this forum