学步园

好水。。以至于我循环的时候都忘了开方。。。

#include <stdio.h><br /> #include <string.h><br /> #include <math.h><br /> bool isPrime[1000001];<br /> long long prime[78500];<br /> long long pn = 0;<br /> void init() {<br /> memset(isPrime, true, sizeof(isPrime));<br /> for(int i = 2; i * i <= 1000000; i++) {<br /> if(isPrime[i]) {<br /> for(int j = i * i; j <= 1000000; j += i)<br /> isPrime[j] = false;<br /> }<br /> }<br /> for(int i = 2; i <= 1000000; i++)<br /> if(isPrime[i]) prime[pn++] = i;<br /> }<br /> int main() {<br /> init();<br /> long long n;<br /> while(scanf("%lld", &n) != EOF && n >= 0 ) {<br /> for(long long i = 0; i < pn; i++) {<br /> if(n == 1) break;<br /> while(n % prime[i] == 0) {<br /> printf(" %lld/n", prime[i]);<br /> n /= prime[i];<br /> }<br /> }<br /> long long m = sqrt(n + 0.5);<br /> for(long long i = prime[pn - 1] + 1; i <= m; i++) {<br /> if(n == 1) break;<br /> while(n % i == 0) {<br /> printf(" %lld/n", i);<br /> n /= i;<br /> }<br /> }<br /> if(n != 1) printf(" %lld/n", n);<br /> printf("/n");<br /> }<br /> return 0;<br /> }