codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<bits/stdc++.h> #define inf 1000000 #define till 50000 using namespace std; static long long int primes[inf]; vector < long > store; vector < long > factors; bool check(int N,int pos) { return (N & (1 << pos)); } int sett(int N,int pos) { return (N = N | (1 << pos)); } void bitSieve() { for(long i=3; i*i < inf; i+=2) { if(!check( primes[i>>5], i&31 )) { for(long j = i*i; j<inf; j+= (i<<1)) { primes[j >> 5] = sett(primes[j >> 5], j&31); } } } store.push_back(2); for(long i=3; i<inf; i+=2) { if(!(check(primes[ i>>5 ],i&31))) { store.push_back(i); } } } void facts(long n) { bool sign = 0,fuck=0; if(n<0) { sign = 1; n = (-1)*n;} long save = n; // Copying the n for setting ok the output format for(long i=0; i<=70000; i++) { while( !(n % store[i]) ) { n = n / store[i]; factors.push_back(store[i]); fuck = 1; } if(n==1) break; } long sz = factors.size(); if(sign) printf("-%ld = -1 x ",save); else printf("%ld = ",save); if(n != 1 || fuck == 0) { printf("%ld\n",save); return; } for(long i=0; i<sz; i++) { if(i == sz-1) { printf("%ld\n",factors[i]); } else { printf("%ld x ",factors[i]); } } factors.clear(); } int main() { bitSieve(); long long int a; while(scanf("%lld",&a)) { if(!a)break; facts(a); // cout << store[46340] << endl; } return 0; }
Private
[
?
]
Run code
Submit