Think like a programmer: Problem Solving in C (Beginner)
Objective: Understand the logic and process of developing a program.
Problem: Find the prime numbers of a certain number X.
- How would we solve this problem in real life?
Example: X = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
FINISH: 2*2*2*2*2 = 32
- What concepts should we know before we begin writing our program?
Before you write any programs, you should know the basics of the language your writing on, in this case C. If you're reading this, I assume you know about data types, loops, etc. (the basics).
- How can we imitate this prime number finding procedure in a program?
Well, first we might want to notice some patterns. We see that we start with a number X, and we divide that by a prime number Z. The result we call it Y. If the division X / Z gives a whole number Y (without any remainder), then we divide Y by Z, until we get a remainder in the division. When we get a remainder, we increment Z to the next prime number, unless Y is also a prime number (this is hard to figure out, unless you have a list of prime numbers).
- We know what to do, now lets identify patterns!
Now that we know the process to find the prime numbers of X, we want to find a pattern so we can loop through it instead of having to manually code in the same thing over and over again.
Referring to the previous step, let Y be a variable, X a constant, and Z an array of prime numbers (constants).
Let Z have the following values: 2, 3, 5, 7, 11 (a total of 5 different values). We access the first value by saying Z[0], which equals 2. Then Z[1] = 3, and so on until Z[4] = 11.
We see that we divide Y by Z[index] and assign Y the value of Y / Z (Y = Y/Z) if and only if Y % Z is equal 0 (the remainder of Y / Z is 0). If Y / Z is not a whole number (without decimals, in other words, with remainder) we proceed to the next prime number.
Procedure:
- Once we have our environment set, we can proceed by initiating variables that we know are necessary. After that the first thing we should do is find out what is the number X we are finding the primes for:
Code:
#include <stdio.h>
//main() is what the program executes when you launch it...
int main() {
char input_buffer[20]; //A string where we store the input from the user (Number X)
unsigned int factorial_list[5]; //An array of u ints (no negatives, so we can have a 2^32 max. number, google C data types for more info)
unsigned result[128]; //Store the primes with find from number X, we can store 128 of them... more than enough...
unsigned int x = 0; //Where we store the integer the user inputs
unsigned int y = 0; //This is the changing variable we talked about
unsigned int index_A = 0; //Index used to navigate through factorial_list[]
unsigned int index_B = 0; //Index used to navigate through the result[]
//Initiate the values for the factorial_list
factorial[0]=2;
factorial[1]=3;
factorial[2]=5;
factorial[3]=7;
factorial[4]=11;
//Initiate values for result[]
for(index_B; index_B < 128; index_B++)
{
result[index_B] = 0;
}
index_B = 0;
printf("Enter a positive 32bit integer number: "); //I announced the restraints for the number X
if(fgets(input_buffer, sizeof input_buffer, stdin) == 1) //If a int is in input...
{
if(sscanf(input_buffer, "%d", &x) != NULL) //If we take the number and assign it to int x successfully (&x is the address to the int x, so we assign the put the value in that address, google pointers)
{
y = x; //Assign y the value of number X
}
}
return 0;
}
- If the input passes through the if statements, then it's a valid integer to work with. We already assigned Y the value of X, so now all that is left is create the loop.
Code:
//Import standard input and output C library
#include <stdio.h>
//main() is what the program executes when you launch it...
int main() {
char input_buffer[20]; //A string where we store the input from the user (Number X)
unsigned int factorial_list[5]; //An array of u ints (no negatives, so we can have a 2^32 max. number, google C data types for more info)
unsigned result[128]; //Store the primes with find from number X, we can store 128 of them... more than enough...
unsigned int x = 0; //Where we store the integer the user inputs
unsigned int y = 0; //This is the changing variable we talked about
unsigned int index_A = 0; //Index used to navigate through factorial_list[]
unsigned int index_B = 0; //Index used to navigate through the result[]
//Initiate the values for the factorial_list
factorial[0]=2;
factorial[1]=3;
factorial[2]=5;
factorial[3]=7;
factorial[4]=11;
//Initiate values for result[]
for(index_B; index_B < 128; index_B++)
{
result[index_B] = 0;
}
index_B = 0;
printf("Enter a positive 32bit integer number: "); //I announced the restraints for the number X
if(fgets(input_buffer, sizeof input_buffer, stdin) != NULL) //If a int is in input...
{
if(sscanf(input_buffer, "%d", &x) == 1) //If we take the number and assign it to int x successfully (&x is the address to the int x, so we assign the put the value in that address, google pointers)
{
y = x; //Assign y the value of number X
for(index_A=0; index_A < 5; index_A++) //Do while index_A is less than 5, because 5 is the total amount of prime numbers in the list.
{
if(y % factorial[index_A] == 0 && y != 0) //if the remainder of y/primenumber = 0 AND y is NOT 0. Why? Because if y =0, then y/prime = 0 remainder 0.
{
y = y / factorial[index_A]; //Assign new value to Y
result[index_B] = factorial[index_A]; //store a valid prime in the result array
index_A--; //decrease index_A so we repeat with the same factor again
index_B++; //increase index_B so we don't overwrite the current result in the next entry
}
}
}
}
return 0;
}
- Lastly, we display and prove that our result is correct:
Code:
//Import standard input and output C library
#include <stdio.h>
//main() is what the program executes when you launch it...
int main() {
char input_buffer[20]; //A string where we store the input from the user (Number X)
unsigned int factorial[5]; //An array of u ints (no negatives, so we can have a 2^32 max. number, google C data types for more info)
unsigned result[128]; //Store the primes with find from number X, we can store 128 of them... more than enough...
unsigned int x = 0; //Where we store the integer the user inputs
unsigned int y = 0; //This is the changing variable we talked about
unsigned int index_A = 0; //Index used to navigate through factorial
unsigned int index_B = 0; //Index used to navigate through the result[]
//Initiate the values for the factorial array
factorial[0]=2;
factorial[1]=3;
factorial[2]=5;
factorial[3]=7;
factorial[4]=11;
//Initiate values for result[]
for(index_B; index_B < 128; index_B++)
{
result[index_B] = 0;
}
index_B = 0;
printf("Enter a positive 32bit integer number: "); //I announced the restraints for the number X
if(fgets(input_buffer, sizeof input_buffer, stdin) != NULL) //If a int is in input...
{
if(sscanf(input_buffer, "%d", &x) == 1) //If we take the number and assign it to int x successfully (&x is the address to the int x, so we assign the put the value in that address, google pointers)
{
y = x; //Assign y the value of number X
for(index_A=0; index_A < 5; index_A++) //Do while index_A is less than 5, because 5 is the total amount of prime numbers in the list.
{
if(y % factorial[index_A] == 0 && y != 0) //if the remainder of y/primenumber = 0 AND y is NOT 0. Why? Because if y =0, then y/prime = 0 remainder 0.
{
y = y / factorial[index_A]; //Assign new value to Y
result[index_B] = factorial[index_A]; //store a valid prime in the result array
index_A--; //decrease index_A so we repeat with the same factor again
index_B++; //increase index_B so we don't overwrite the current result in the next entry
}
}
index_B = 0; //Set index to 0 again...
x = 1; //Set x to 1 so we can multiply all the primes with it and prove if it's right or wrong
printf("\n"); //new line
while(result[index_B] != 0) //While the results haven't ended (remember, we initiated all the array slots with a 0 value, those that have results are not 0s!!)
{
x = x*result[index_B]; //Multiplying all the primes in the results together...
printf("%d*", result[index_B]); //print into screen the multiplication we're doing
index_B++;
}
printf("1=%d",x); //last prime would be 1, that's inferred, but we put it any ways to complete the multiplications, otherwise we would have an extra "*"
printf("\n");
}
}
return 0;
}
That's it, not that hard, eh?
Compiled under GCC and tested in Fedora.
All the work was done by me, Riddle, please don't copy, unless you link back.
