Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
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.
Nice!
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 Smile

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 Smile

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
Page 1 of 1
» All times are GMT - 5 Hours
 
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

 

Advertisement