The task description is here: https://codility.com/demo/take-sample-test/peaks It's also here: Codility Peaks Complexity
First, I tried solving this myself but was only able to come up with what I believed to be a brute force solution. However, it scored 100/100: https://codility.com/demo/results/demoRNWC3P-X4U
Which obviously is completely unsatisfying for me. ;) The outer loop is called for each factor of N (or for each peak, whichever is smaller) and the inner one is called for each peak (just checking if there's a peak in every block). Maybe that's O(N^2), maybe a bit better (since it passes the tests in time limits) but I'm almost sure it's not O(N*log(log(N))).
Then I tried searching for an O(N*log(log(N))) solution but everyone else seems to have a pretty similar solution to mine.
So does anyone have an idea for an O(N*log(log(N))) (or a better one) solution?
Also, if anyone could tell me what complexity my solution has I'd be grateful.
Your code is O(n d(n)) where d(n) is the number of divisors of n. On [1, 100000], d(n) is maximised at 83160 = 2^3 3^3 5 7 11, which has 126 divisors. According to Wikipedia, d(n) is o(n^epsilon) for every epsilon>0, so it grows rather slowly.
To get an O(n log log n) solution, build a partial sum array telling you how many peaks are left of each point. Then you can tell whether there's a peak in an interval in O(1) time. Checking a divisor d then takes O(n/d) time. Adding up n/d over all divisors d is the same as adding up d over all divisors d, and the result is, according to the same Wikipedia page, O(n log log n).