Prime number factorization

Hey everyone!

I was wondering if someone could help me fix two of my algorithms. I am trying to factorize semi-prime numbers by using a brute force method and a square root method.

The brute force method should start by multiplying all odd numbers between 1 and the semi-prime number. Meaning that 1 should multiply 3 then 5 then 7, etc. Then three should multiply 5 then 7 then 9 and so forth. The first number would never multiply a number equal to or less than itself.

Any help at all would be greatly appreciated!

Here is what I have:

1
2
3
4
5
6
7
8
9
10
11
12
bruteForce(int x){
	f1 = 1;
	f2 = f1 + 2;
	while (f1 < x){
		for (f2 = x; f2 <= x; f2-2){
			f1 * f2;
		}
			if (x%f1 == f2 || x%f2 == f1)
				printFactors(f1,f2);
		} f1 = f1 + 2;
	};


For my other algorithm, I want it to get the square root of the semi-prime and then start multiplying odd numbers around it. I made it so that the square root would have to be set to the next even number (in case it was a factor). If the product of the two odd numbers (a * b) is greater than the original semi-prime, I would multiply b by the next smaller number than a. Conversely, if the product of a and b is less than the original semi-prime, it will multiply a by the next odd number larger than b. This will repeat until the two correct factors of the original semi-prime are found.

Algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
SquareRootFactorize(int x){
	int N = x;
	sqrtN = sqrt(N);
	if (isOdd(sqrtN) == true)
		sqrtN = sqrtN + 1;
	f1 = sqrtN - 1;
	f2 = sqrtN + 1;
	cout << sqrtN;
	while (N != n){
		n = multFacts(f1,f2);
		if (N < (f1 * f2))
			f1 = f1 + 2;
		else if (N > (f1 * f2))
			f2 = f2 + 2;
		else if (N = n)
			printFactors(f1,f2);
	}
}
The fun about algorithms is that you sometimes think your brain is bleeding trying to get a glance of what the hell is going on

Giving you the answer wouldn't help you at all (even if you were to understand what's happening)
The key of learning how-to is to come up with a solution yourself and learn the process how to think to get there

Maybe I can point you in a direction and show you that whatever you think the code below is doing isn't what it acutally does.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bruteForce(int x){
	f1 = 1;
	f2 = f1 + 2;  // here you set f2 to 3
	while (f1 < x){ // looks okay
		for (f2 = x; f2 <= x; f2-2){  // and here you set f2 to x which overwrites the 3
			f1 * f2; // I think your heart is in the right place (is x an odd number?)
// if not then you are about to multiply all even numbers from x down to infinity
// you have to save the result of f1 * f2 somewhere here so you use the result for your next iteration
// On top of all that it looks like an infinite loop (since your f2 is getting smaller it will always be <= x  ( btw you wrote f2-2 it should be f2 -= 2)
		}
			if (x%f1 == f2 || x%f2 == f1) // I don't get that 
				printFactors(f1,f2);
		} f1 = f1 + 2; // this seems okay
	};


If you figured this out come back for the second one but don't try to multitask while both Tasks include algorithms ;)

Well I hope this helps you somehow
Last edited on
Topic archived. No new replies allowed.