CODEWITHSUNDEEP
cprime-factoring
user3259344
user3259344

Reputation: 31

How to find out how many times the prime number occurs?

I need to write a program to input a number and output it's factorial in the form in C

4!=(2^3)*(3^1)

5!=(2^3)*(3^1)*(5^1)

I am able to find the prime numbers 2, 3 and 5 but how do i figure out how many times they occur? (^3, ^1, ^1)

Code:

int main() {
    int num,i,count,n;
    printf("Enter to find prime numbers: ");
    scanf("%d",&n);

    for(num = 2; num<=n;num++) {
        count = 0;

        for(i=2;i<=num/2;i++) {
            if(num%i==0)
            {
                count++;
                break;
            }
        }

        if(count==0 && num!= 1)
            printf("%d ",num);
    }
    return 0;
}

Upvotes: 2

Views: 2033

Answers (2)

ssm
ssm

Reputation: 5383

Without going into any code, Ill explain what the problem in the way you are doing things ...

Let us say you want to find the prime factors of the factorial of 5. So you do:

5! = 2 x 3 x 4 x 5 (this is your outer loop (for(num = ...)

Let us say that for a particular iteration, num = 4. Then, you have another iteration in i that checks of each number upto that num/2 is a factor. Now for a small value of 5! this is not a problem. Consider a bigger number like 25!. In this case, your outer loop will be:

25! = 1 x 2 x 3 x ... 22 x 23 x 24 x 25

Now your outer iteration num goes much further. Consider now the number 24. 24/2 = 12. Your program is going to print all factors that divide 24 upto 12, which happen to be 2, 3, 4, 6, and 12. I am sure, that is not what you want.

First, do not attempt to find the factorial for large numbers. You will run into overflow issues. Next, Ill give you some pointers and hope you can solve the problem on your own. Its a very cool problem, so I really hope you are able to solve it:

  1. Study the prime sieve algorithm (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). You will not be using this directly, but only the ideas mentioned here.
  2. Create two arrays. The first one will contain the prime factors, while the next one will contain the total count of the factors occuring in the factorial.
  3. For a particular num u need to be iterating not using the i that you have used but using the values in your prime array. 3.1. Use the method explained by Barmar to find the number of times this num is divisible by the factors, and update the corresponding counts in the count array.
  4. Print out the factors and counts that you have obtained.

Finally, I think its a pretty good question. It teaches you how to not run into overflow errors and still be able to solve problem using the computer. It can teach you dynamic memory allocation and memory management skills, if that is the way you want to go. It also helps you to think critically about a problem. You dont deserve a -1. I have increased your rating.

Have fun programming, and keep thinking critically about each setp in your program.

Cheers!

Upvotes: 3

BLUEPIXY
BLUEPIXY

Reputation: 40145

for(num = 2; num<=n; ++num){
    count = 0;

    while(n % num == 0){
        n /= num;
        ++count;
    }

    if(count!=0)
        printf("(%d^%d)", num, count);
}

Upvotes: 0

Related Questions