How to make it faster ??? Thx...10990 - Another New Function
Moderator: Board moderators
-
jan_holmes
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
10990 - Another New Function
What method should we use in this problem ??? I use sieve... but still TLE... How to make it faster ??? Thx...
How to make it faster ??? Thx...The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN).
(I used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 linear-arrays, or you'll get MLE.)
for each integer v ∈ [1...N],
store the prime factor factor[v] that divides v.
And, another hint :
factorization of 72 can refer factorization of 9, if factor[72] is 2.
(I used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 linear-arrays, or you'll get MLE.)
for each integer v ∈ [1...N],
store the prime factor factor[v] that divides v.
And, another hint :
factorization of 72 can refer factorization of 9, if factor[72] is 2.
Sorry For My Poor English.. 
Output from my AC program:polone wrote:what should the test case be?
2
2 2000000
72 72
Code: Select all
33829803
5
