沒用sqrt就TL,
用sqrt變超快!
看來我的i * i <= n以後都要寫,
i <= sqrt(n)了 。
/* ACM 583 Prime Factors * mythnc * 2011/11/17 22:56:12 * run time: 0.340 */ #include <stdio.h> #include <math.h> void factor(int); int print(int, int); int main(void) { int n; while (scanf("%d", &n) && n != 0) { printf("%d = ", n); if (n < 0) { printf("-1 x "); n *= -1; } factor(n); } return 0; } /* factor: find prime factor and print it */ void factor(int n) { int i; /* even */ while (n % 2 == 0 && n != 1) n = print(n, 2); if (n == 1) return; /* odd */ for (i = 3; i <= sqrt(n) && n != 1; i += 2) while (n % i == 0 && n != 1) n = print(n, i); if (n == 1) return; /* prime */ if (n != 1) printf("%d\n", n); } /* print: print prime and return n */ int print(int n, int i) { n /= i; if (n == 1) { printf("%d\n", i); return 1; } else printf("%d x ", i); return n; }
沒有留言:
張貼留言