M.A.H.M.O.O.D's blog

Help with math related problem
By M.A.H.M.O.O.D, history, 8 years ago, In English

Hi codeforcer.

So let's cut right to the chase given N where 1<=N<=5000000 find the number of the prime factors the make up N.

e.g. 6=2*3 =>the answer for 6 is 2.

e.g. 12=2*2*3 =>the answer for 12 is 3.

I think it's called prime factorialzition or prime decomposition I'm not sure since my English with math vocabulary is worse than my coding skills.

Please keep it simple.

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

for ( int i=2 ; i<=n ; i++ ) { { while ( n%i==0 ) { n/=i; c++; } } }

the answer is c

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes that's right but you see I have to make this operation 1000000 times for different integers so your solution will take long but thank you anyway.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can make the worst case performance (n is actually prime) faster simply by testing up to sqrt(n)+1 instead of just n.

    But yeah, if you're going to be making tons of queries, then tweety's preprocessed sieve would be the way to go!

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it 
int factor[MAXN];
bool prime[MAXN];

int main() {
	memset(prime, 1, sizeof prime);
	prime[0] = prime[1] = false;
	for (int i = 2; i < MAXN; i++) {
		if (!prime[i]) continue;
		factor[i] = i;
		for (int j = i + i; j < MAXN; j += i) {
			prime[j] = false; // sieve
			factor[j] = i;
		}
	}
	int x;
	cin >> x;
	int ans = 0;
	while (x > 1) {
		cout << factor[x] << endl; // prints the factors
		x /= factor[x];
		ans++;
	}
	cout << "num = " << ans << endl;
}

I think the code is self-explanatory
UPD: the above comment has complexity O(n). My code has O(nlogn) preprocessing and O(logn) per query. (n should be less than MAXN)
by query I mean number to check

→ Reply