Prime Factors

[whiteflip]

I'm trying to make a program for my calculator that will figure out Prime Factors of a particular number but I am having strangely the hardest time getting one to work. I have one that figures out all the Prime numbers between a certain integer range but its been so long since I wrote anything.

Anyways, Who can do what I seemingly can't do? C++, Pascal, Java, Delphi, JavaScript, Basic whatever you feel like working with. Should be a simple exercise to pass the time.

[shakey_snake]

I used to be a TI 83+ nerd...

[ujay]

First use your prime number generator to check it's not already prime.

Then succcessively take the numbers from your PNG and test for exact division using something like MOD=0, if true use DIV to determine the remaining dividend and if > 1 apply the same process again (starting with the largest number you reached on the previous calc.) collect your results together. You only need to use values up to SQR(n).

Or something like that

UJ

[shakey_snake]

http://www.ticalc.org/search/

[xzxzzx]

Yay! Stupid/fun coding project:

code:
// stupidfun.cpp : Yay!

//



#include <stdio.h>



bool IsPrime(int n)

{

	for(int i = (n - 1); i > 1; --i){

		if((n % i) == 0) {

			return false;

		}

	}

	return true;

}



void PrintPrimeFactors(int n)

{

	int x = 1;

	for(int i = (n - 1); i > 1; --i){

		if(((n % i) == 0) && IsPrime(i)){

			printf("A prime factor #%d is: %d\n", x++, i);

		}

	}

}



int main(void)

{

	PrintPrimeFactors(6);

	getchar(); // for a pause

	return 0;

}

[edit]Note: does not print "1" as a prime factor. If you'd like it to, simply:
change
"i > 1"
to
"i > 0"
in PrintPrimeFactors().[/edit]

[zootm]

Apparently 1 isn't strictly a prime number. Which is good, because in what I was gonna do, it would lead to an infinite loop. Since xzxzzx has basically done it, I'll just base my implementation roughly on his...

code:


// in Java, incidentally.



class Fun {

    static boolean isPrime (int n) {

	boolean prime = true;

	for (int i = 2; i < n; i++) {

	    if (n%i == 0) {

		prime = false;

		break;

	    }

	}

	return prime;

    }



    static String getPrimeFactorisationAsString (int n) {

	int x = 1;

	int j;

	String result = "";

	for(int i = (n - 1); i > 1; --i) {

	    if ((n%i == 0) && isPrime(i)) {

		for (j = 2; true; j++) {

		    if (!((n%(Math.pow(i,j)))==0)) break;

		}

		result += "(" + i + "^" + j-1 + ")";

	    }

	}

	if (result.equals("")) result = new String ("(" + n + "^1)");

	return result;

    }

    

    public static void main (String [] args) {

	if (args.length != 1) {

	    System.out.println ("Please give me a number.");

	} else {

	    int number = Integer.parseInt(args[0]);

	    System.out.println ("The prime factorisation of " + number + " is " + getPrimeFactorisationAsString(number));

	}

    }

}

[xzxzzx]

[edit]Nevermind, stupid question.[/edit]

[whiteflip]

I'm pretty sure this is what a crappy Ti-83 version would look like. Very unoptimized code

code:


ClrHome

DelVar P

DelVar X

DelVar Y

DelVar Z

DelVar L1

DelVar L2

{0}->L2

{1}->L1

DelVar lPrime

Disp "PRIME FACTORS"

Input "INTEGER: ",P

abs(int(P))->P

If P <= 2

Goto 01

For (X,P-1,1,-1)

If P/X=int(P/X)

Then

1->Y

For (Z,1,int(X/2))

If gcd(Z,X)!=1

0->Y

End

If Y=1

Then

Disp X

{X}->L2

If Z!=1

augment(L1,L2)->L1

End

End

End

L1->lPrime

DelVar X

DelVar Y

DelVar Z

DelVar L1

DelVar L2

Disp "PRIME FACTORS OF",P,lPrime

DelVar P

Return

Lbl 01

Disp "INTEGER TO SMALL"

Return

[shakey_snake]

DelVars don't need a character return
and don't close your () or you ""


gotta love TiBasic

[will]

code:


fun facts(x) = let fun f(1,n) = []

                     | f(x,n) = if x mod n = 0 then n::f(x div n, n) else f(x, n+1);

               in f(x,2) end;

This implementation in MosML is clearly the best. The function facts() takes a number and gives a list of its prime factors.

[edit] here is a java version that works exatly the same, but is much less tearse.

code:
public class PrimeFactors {	

	public static String findPrimes(int x) {

		return doFindPrimes(x,2);

	}

	

	private static String doFindPrimes(int number, int minfactor) {

		if(number == 1) return "";

		if(number % minfactor == 0) return minfactor + " " + doFindPrimes(number / minfactor, minfactor);

		return doFindPrimes(number, minfactor + 1);

	}

}

[/edit]

[dlinkwit27]

Y'all made this much more difficult than it is. This is how I have it on my calc (I'm doing from memory, so systen may be a bit off, but you'll get the idea)

code:


DelVar Q

DelVar R

r=2

DelVar L1

Input "Number: ",P

abs(int(P))->P

Lbl 1



if Q<P-2

then

R=2

For (R,R<P-1,r+1)

if mod(p/r)=0

then

r->L1

goto1

else

end



end





Disp L1

End

I'll look more closely @ the code when I get my calc back (my g/f has it)

[xzxzzx]

Whaa? I don't know TiBasic, dlinkwit27, but I don't think that'd do what whiteflip wants.

[edit]Have you tested that Java, will? It doesn't look like it'd work to me.[/edit]

[dlinkwit27]

Originally posted by xzxzzx
Whaa? I don't know TiBasic, dlinkwit27, but I don't think that'd do what whiteflip wants.

[edit]Have you tested that Java, will? It doesn't look like it'd work to me.[/edit]

basicly what it does is takes in a number (p) , then divides that number by increaseing amounts starting @ 2 (r) until the remainder is 0. If the remainder is 0, it storest that number (r) in a list, then does it again. I may have used a while loop. I'm not sure.

I should change the for loop tho. The for loop should be
int(p/2) instead of p-1\

/edit
crap. I see wht the problem is. I failed to reduce the
number you start with. Let me change that....

again, the syntax may be a bit off, but you should be able to figure it out.

code:


DelVar L1

Input "Number: ",P

lbl 1

2->D

while(D<int(P/2) and mod(P/D))



D+1>D

end

P/D->P

D->L1

goto 1

End

Disp L1

End

[shakey_snake]

yeah, use a while() instead of the Lbl:goto.
Leaving a conditional open is not a good Idea.

[will]

Originally posted by xzxzzx
Have you tested that Java, will? It doesn't look like it'd work to me.

If by working you mean take a number and give a list of prime factors in numerical order then yes.
For example, given the input 2132 it gives the output:
2 2 13 41
and, of course 2*2*13*41 = 2132.

The given number is x.
minFactor starts at 2, the smallest prime number.
If the number has a factor of 2, it adds it to the list and does the same for x/2.

If there is no factor of 2, then it tries 3, then 4. 4 is not prime, so this test is redundent because all factors of 2 have been taken out already, so it quickly skips to the next.

Here is an iterative version that may be easier to understand.

code:
	public static String findPrimesIter(int x) {

		int minfactor = 2;

		String ret = "";

		while(x > 1) {

			if(x % minfactor == 0) {

				ret += minfactor + " "; // add this factor to the list

				x /= minfactor; // remove this factor from x now it is the list

			}

			else ++minfactor; // no more factors of this, so try the next.

		}

		return ret;

	}

[zootm]

Originally posted by will
This implementation in MosML is clearly the best. The function facts() takes a number and gives a list of its prime factors.

SML is the best language ever, yeah

Edit: And that's how I was gonna do the system, although I was gonna start it at 1 (thus the infinite loop). Wasn't thinking straight!

[xzxzzx]

...

So can't remember my math. My program isn't what one is looking for - I was just printing all "factors" (using the idiot definition) that happened to be prime, not the Prime Factors...

[zootm]

Strictly speaking, they're the same thing, you just weren't showing the magnitudes.

[xzxzzx]

True.

[whiteflip]

If I could only use my palm pilot on test. The calculator I downloaded for it is so awesome. Yeah I could do Delvar X,Y,Z but I grew up with the other way. My memory cleanup program has it the more efficent way.

I have no idea how to get a program to the point of 2,3^5,7 so oh well.