Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
3.3k views
in Technique[技术] by (71.8m points)

Prime Factorisation + prime number in C

Well I have been assigned to do the prime factorisation for composite numbers, but the problem is I have hard-coded it till prime numbers:2,3,5,7,11,13,19 and I want to make it general.

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void prime(int flag,int num);
int main()
{
    int num, flag, i, div;
    printf("Enter your number: ");
    scanf("%d", &num);
    flag = 1;
    prime(flag, num);
    printf("Press any key to exit.");
    getchar();
    return 0;
}

void prime(int flag, int num)
{
    void factor(int num, int i);
    int sq, i, square; 
    sq = abs(sqrt(num));

    if (num == 2)
          flag = 1;  
    else
        for (i = 2; i <= sq; i++)
     {
         if (num % i == 0)
         {
             flag = 0;
             break;
         }
         else
             flag = 1;
     }
    if (flag == 1)
        printf("
%d is a prime number", num);
    else
    {
        printf("
%d is not a prime number
", num);
        factor(num, i);
    }
}      

void factor(int num, int i)
{
    for (i = 2; i <= num; i++)
    {
        again:
        if(num % i == 0)
       {
           num = num / i;
           printf("%d x", i);
           if (num != (2||3||5||7||11||17||19))
               goto again;              
       }   
    }
    printf("1

");
}

P.S.:Try to make it as simpler as possible. The problem is after dividing it with smallest prime. i.e. 2 the next step should be check the number whether it is a prime or not. If not, then factorise it but I dont know how to do it. Plz help. Thx in advance.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)
#include <stdio.h>

void factor(int num);

int main(void){
    int num;

    printf("Enter positive number(more than 1): ");
    if(1 != scanf("%d", &num) || num < 2){
        printf("invalid input!
");
        return -1;
    }
    scanf("%*[^
]");scanf("%*c");//clear upto line end

    factor(num);

    printf("Press any key to exit...");
    getchar();
    return 0;
}

void factor(int num){
    int i, flag = 0;

    if(num == 2){
        printf("
%d is a prime number
", num);
        return ;
    }
    while(!(num & 1)){
        if(!flag)
            printf("
%d is not a prime number
", num);
        flag = 1;
        printf("2 x ");
        num >>= 1;
    }
    for (i = 3; i*i <= num; i += 2){
        while(num % i == 0){
            if(!flag)
                printf("
%d is not a prime number
", num);
            flag = 1;
            printf("%d x ", i);
            num /= i;
        }
    }
    if(!flag)
        printf("
%d is a prime number
", num);
    else if(num != 1)
        printf("%d x 1

", num);
    else
        printf("1

");
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...