Prime Factorization in C++ - Problem with Factors that are Square Roots

Dimmins (3)
Greetings

This is my first time posting in any programming forum, so I hope I can pose my problem to you correctly.

This is my 6th week in my first programming class, having never programmed before in my life. In order to catch up, I've been trying to write out practice problems that I believe I can solve (cash register machine and the like). This particular problem is finding whether an input number is prime, and if it is not, find the factors of the number and the number of factors.

This is not a homework assignment, I assure you, but just a way of testing my abilities.

We just covered how to do loops, so we do not know how to do void functions, classes, or anything of the sort. The anstolower function was created by my professor and I understand the concept but could not duplicate it without looking at it.

We are using Visual Studio 2010 in class on a double booted 64-bit Windows system on a MacBook Pro.

My Question:

Line 75 is the problem area. The if (test == halfNum) section is never used. When inputting 100, when the loop gets to test=10, it displays "10 and 10 are factors of 100", then increasing the counted number of factors by 2 rather than 1. Since this problem arose, the downstream information display area (line 112) is also messed up.

The code compiles and works perfectly (assuming a valid positive integer is input) for all numbers except for values that are perfect squares. Everything in commented and the two problem areas are set apart by upper cased comments on to the left hand side.

Any suggestions on formatting, ways of commenting on the code, or general tips are also appreciated.

Thank you for any help!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>

using namespace std;

string anstolower(string s)
{
	string result = "";
	for(int i = 0; i < s.length(); i++)
	{
		result += tolower(s[i]);
	}
	return result;
}

int main()
{
// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
//                                          VARIABLES
// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
	unsigned int num, test;				// Number user chooses to test, value testing primality.
	unsigned int factor, outcome;			// Number of factors found, value to determine if a factor.
	unsigned int halfNum;				// Half of the input number.
	int primeNum=1;					// Number of prime factorizations performed.
	string input;					// User input for Yes/No question.
	string low;					// tolower'd form of input.

// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
//                                          GREETINGS
// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===

// Welcome the user.
	cout << "\n\n    =====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-====="
	<< "\n                 ~!~ Welcome to the Prime Factorizationing ~!~"
	<< "\n    =====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-====="
	<< "\n\n This program will calculate the primality of a number, and if it is"
	<< "\n not prime, the factors and number of factors of the input number.";

// START OF PROGRAM END CHECK LOOP
	do {
	// START OF PROGRAM LOOP.
		do {
		// Reset testing variables to allow computation for new numbers.
			test=2;				// Sets the starting divisor to 2 to begin testing for factors.
			factor=0;			// Sets the number of factors of the input number to zero.

		// Numbers each factorization for easier following.
			cout << "\n\n\n -Prime Number Test # " << setw(2) << primeNum << "-";
		// Increases the number for record of later factorizations.
			primeNum ++;

		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
		//                                         USER  INPUT
		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===

		// Prompt user for number to be tested.
			cout << "\n\n Please input a number to calculate if it is prime. : ";
			cin >> num;

		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
		//                                         CALCULATION
		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===

		// START OF FACTOR FINDING LOOP.
			do {
				halfNum = num/2;
			// If outcome does not equal zero, test was a factor of the number.
				outcome = num%test;

			// If outcome does not equal zero, shows the user the found factor.
				if (outcome == 0) {

// PROBLEM WITH CALCULATION OF SQUARE ROOTS.

				// If test is equal to half of the input number and it is a factor, it is the square
				// root of the number, so only 1 factor was found.
					if (test == halfNum) {
					// The test number was the factor found, so show test.
						cout << "\n " << setw(10) << test << " is a factor of " << num << ".";
					// There was only 1 factor, so factor increases by 1.
						factor++;
					}

				// If the found factor was not half of the input number, then two factors were found.
					else {
					// Test number and its sister factor, found by (num/test), are displayed.
						cout << "\n " << setw(10) << test << " and " << (num/test) << " are factors of "
							<< num << ".";
					// There were 2 factors found, so factor increases by 2.
						factor += 2;
					}
				}

			// Increases the test variable by 1 for the loop to continue.
				test++;

		/*	(test <= (num/test)) keeps test values smaller than otherwise since the numbers over num/2 
			were previously calculated. */
		// END OF FACTOR FINDING LOOP
			} while (test <= (num/test));

		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===
		//                                        FINAL OUTCOME
		// ===-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====!=====-===	

		// Inform user of the outcome.
			cout << "\n\n    =====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====";

// SINCE THERE IS AN UNRESOLVED PROBLEM WITH SQUARE ROOTS UPSTREAM, THIS SECTION IS FLAWED.

		// If there was only 1 factor, display that factor (test was increased by 1 before the loop
		// terminated, so to find the factor it is (test-1).
			if (factor == 1) {
				cout << "\n The only factor of " << num << " is " << (test-1) << " (excluding"
				<< " 1 and " << num << ").";
			}
		// If there was more than one factor, display the number of factors found.
			else if (factor != 0) {
				cout << "\n There are " << factor << " factors of " << num << " (excluding"
				<< " 1 and " << num << ").";
			}
		// If there were no factors, input number is prime.
			else {
				cout << "\n The input number is prime." << endl;
			}

			cout << "\n    =====-=====-=====!=====-=====-=====!=====-=====-=====!=====-=====-=====";

		// Prompt for calculation of primality of a new number or to terminate program.
			cout << "\n\n Would you like to calculate the primality of a new number? Yes or No? : ";
			cin.ignore();
			getline(cin,input);

		// Validate input.
			low = anstolower(input);
			while((low != "y") && (low != "yes") && (low != "n") && (low != "no")) {
				cout << " Invalid choice.  Please choose Yes or No. : ";
				getline(cin,input);
				low = anstolower(input);
			}

	// END OF PROGRAM LOOP
		} while ((low == "yes") || (low == "y"));

	// Check to see if the user wanted to terminate program.
		cout << "\n Are you sure?  Type Yes to close program, No to calculate the primality of a"
		<< "\n\tnew number. : ";
		getline(cin,input);

	// Validate input.
		low = anstolower(input);
		while((low != "y") && (low != "yes") && (low != "n") && (low != "no")) {
			cout << " Invalid choice.  Please choose Yes or No. : ";
			getline(cin,input);
			low = anstolower(input);
		}

// END OF PROGRAM END CHECK LOOP
	} while ((low == "no") || (low == "n"));

	return 0;
}
helios (10126)
If test is equal to half of the input number and it is a factor, it is the square root of the number, so only 1 factor was found.
Where did you get this (false) property from?

sqrt(x) = x/2
(square both sides)
x = 1/4*x^2
1/4*x^2 - x = 0
x = (-b +- sqrt(b^2 - 4*a*c)) / (2*a)
(+)
x = (1 + sqrt(1)) / (1/2)
x = 2 * (1 + sqrt(1))
x = 2 * (1 + 1)
x = 4

(-)
x = (1 - sqrt(1)) / (1/2)
x = 2 * (1 - 1)
x = 0

The only two numbers whose square roots are equal to their halves are 0 and 4. Try to think of a better way to find if n is the square root of m.
Tip: don't overthink it. Use the first check you can think of.

One note on style: your commenting is excessive. It makes your code harder to read because all that fluff has to be filtered out. Try to turn it down a notch, especially the "===-=====!=====-==" decorations. Things like that should appear at most once every thousand lines.
Last edited on
Chervil (806)
It looks to me as though the square root is calculated as x/2.
This is only valid when x == 4.

A more appropriate way,
1
2
3
4
5
 
result = number / factor;
if (result == factor) 
{
    // factor is square root of number
}


As for the overall style, putting plenty of comments in the code is good, but it's a good idea to keep them concise and meaningful, and not merely repeating what the code itself says.

For example this:
1
2
 
    // Increases the test variable by 1 for the loop to continue.
    test++;


could be replaced by this:
 
 
    test++;    // Next divisor



Last edited on
Chervil (806)
@helios
Agreed :)
Dimmins (3)
Thank you for your responses. After reading over the critiques if((test*test) == num) and while (test <= (num/test)) is what I was looking for for those two sections. Completely didn't need halfNum anymore. In the wee hours of the morning, logic seems to go all squirrelly.

@helios
I completely did not think to try and write it out mathematically. That helped quite a bit.

Writing different parts of the code at different times caused me to comment on everything so I could put it all in the right order (hence the large obnoxious dividing areas). As I get better at coding I think I'll learn what is useful to comment and what is not necessary.

@Chervil
The small code you posted, along with helios reminding me of the quadratic formula, helped.

Like I said above, a lot of it has to do with me remembering what each part of the code actually does. The example is great, so I'll go back and butcher the comments with readability more in mind.

Thanks again!
Last edited on
Chervil (806)
Actually, I tend to put comments in my code while I'm working on it, to remind myself of what the particular section of code is intended to achieve. Sometimes the comments can remain after the code is completed, other times, some pruning or deletion is needed.

I think you'll find your style gradually changes as you progress with time and practice.
Dimmins (3)
That was my intention, but since I was posing a question to people that already understand coding much more thoroughly, I could have removed them beforehand. After pruning the comments, the program is down to 104 lines with no comment taking more than one line and most are off to the side.

I definitely believe it. In just the past few weeks the style has changed, especially after today.
Topic archived. No new replies allowed.

C++

Forum