/* primes.c Compute the prime factorization of an integer. */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include void prime_factorization(long x) { long i; /* counter */ long c; /* remaining product to factor */ c = x; while ((c % 2) == 0) { printf("%d\n", 2); c = c / 2; } i = 3; while (i <= (sqrt(c) + 1)) { if ((c % i) == 0) { printf("%ld\n", i); c = c / i; } else { i = i + 2; } } if (c > 1) { printf("%ld\n", c); } } int main(void) { long p; while (scanf("%ld", &p) != EOF) { printf("prime factorization of p=%ld \n", p); prime_factorization(p); } return 0; }