Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<math.h> // math library to use the sqrt() (returns the square root of a number)
- //and the ceil() (rounds up the float to the just higher integer
- //note: to compile properly we have to use the -lm flag to link the math library to the executable
- //ex: gcc prog.c -o out -lm
- void minimum(int min){
- printf("Minimum: %d\n",min);
- }
- void maximum(int max){
- printf("Maximum %d\n",max);
- }
- void printdivisors(int n){
- for(int i = 1; i <= n/2; i++) { //for every number i in the range [1,n/2] (if n is even) or [1,n/2-1] if n is odd
- //we check if the remainder of the division n/i is zero. If it is, i is a
- //divisor of n and we print it
- if(n%i == 0){
- printf("%d is a divisor of %d\n",i,n);
- }
- }
- printf("%d is a divisor of %d\n",n,n); //every number is a divisor of itself so we print the number as well
- }
- int checkprime(int n){ //returns 0 if number is not a prime, 1 if number is a prime
- if(n == 1)
- return 1; //1 is a prime number
- if(n==2)
- return 1; //2 is a prime number
- if(n%2 == 0)
- return 0; //if the number is divisible by 2 and is not 2 then it is not a prime number
- for(int i = 3; i <= ceil(sqrt(n)); i +=2){ //if a number is not prime, mathematics guarrantee that some factor other than
- //the number itself will be found in the range [2,sqrt(n)]. Since we have already
- //checked for the number two we begin from 3 and since we have already checked
- //out all of the even numbers we add 2 everytime to an odd number so that we
- //only check the odd numbers. Thus, we are saving time and effort.
- if(n%i == 0){
- return 0;
- }
- }
- return 1;
- }
- void printprimefactors(int n){
- //printf("%d 's prime factors are: ",n);
- for(int i = 2; i<= n/2; i++){ //in this function we combine the divisors of a number with the checkprime() function we
- //already implemented. We simply find all of the divisors of a number and if they are prime
- //we print them out
- if(n%i == 0){
- if(checkprime(i)){
- printf("%d ",i);
- }
- }
- }
- printf("\n"); //print a newline in the end
- }
- //this is the nightmare difficulty leve function
- //here we begin as in the printprimefactors() function by finding all of the prime divisors of the given number
- //we have a temporary variable temp in which we store the value of n for every iteration of the algorithm
- //everytime we find a prime factor, we divide temp by that factor until:
- //a)the division temp/i has a non zero remainder
- //b)the number temp becomes smaller than the prime factor
- //so, for every iteration of this algorithm we simply print out that factor however many times the algorithm runs
- //everytime we print that factor, we update the value of temp to be the result of the division temp/i
- //that way we can actually get how many times is that prime factor used, and since the factors are prime we
- //do not have to worry about their multiples
- //at the end of each factor cycle we restore temp to the original n value so that we don't use the small value
- //that was left behind from the previous computation
- void printadvprimefactors(int n){
- //char* s = printprimefactors(n);
- int temp = n;
- for(int i = 2; i<= n/2;i++){
- if(n%i == 0){
- if(checkprime(i)){
- while(temp%i == 0 && temp>i){
- printf("%d ",i);
- temp = temp/i;
- }
- }
- }
- temp = n;
- }
- printf("\n");
- }
- int main(){
- int min = 0; //we use these two variables to hold the biggest and smallest number we enter
- int max = 0;
- while(1){ //forever loop
- int a; //we read our input here
- scanf("%d",&a);
- //printf("%d\n", a);
- if(a>max)
- max = a;
- if(min>a)
- min = a;
- minimum(min);
- maximum(max);
- printdivisors(a);
- //printf("%d\n", checkprime(a));
- if(checkprime(a)){ //it was easier to implement the checkprime() function returning 1 and 0
- //rather than having it print the whole string. that way we can reuse it in the
- //printprimefactors and printadvprimefactors functions
- printf("%d is a prime!\n", a);
- }
- printprimefactors(a);
- printadvprimefactors(a);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement