Блог пользователя M.A.H.M.O.O.D

Help with math related problem
Автор M.A.H.M.O.O.D, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

the answer is c

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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!

    → Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится 
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

→ Ответить