ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1118. Nontrivial Numbers

Time limit exceeded
Posted by Daniil 23 Oct 2015 01:20
Подскажите, как сократить время работы программы?
[code deleted]

Edited by moderator 19.11.2019 23:42
Re: Time limit exceeded
Posted by Ehsan Raeyatpisheh 24 Oct 2015 00:57
Re: Time limit exceeded
Posted by nadinne 27 Oct 2015 09:15
First you should rewrite function which counts sum of divisors: for (i=2;i*i<=n;i++)...,
second you shouldn't compute triviality of all numbers in [i,j]: just for numbers from j downto first prime number>=i, and of course take into account that triviality(1)=0.