the editorial of this question says that find all the prime numbers less than n and then find all those numbers among them which are of the form 4k+1 . since n is very large , so i am getting tle . plz help me to solve this. https://www.codechef.com/OCT15/problems/ADTRI/ my solution  https://www.codechef.com/viewsolution/8536013 asked 13 Oct '15, 15:13

The question has been closed for the following reason "The question is answered, right answer was accepted" by va1ts7_100 16 Oct '15, 19:44
@va1ts7_100 By doing this you just need to check whether $Nth$ multiple in the array is marked or not. Here is my solution using sieve. answered 14 Oct '15, 15:23
thanks @rjohari... :) , i understood the solution finally ..!
(14 Oct '15, 22:25)
u r welcome :)
(14 Oct '15, 23:39)

@va1ts7_100 We need to find prime numbers only up to square root of 'n' because any composite number beyond this will already be crossed off. This'll leave you with only primes between square root n and n. Best thing to do, pick an example! Say n =40. Square root n, rounded down to closest integer, 6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Rule: pick the first prime number, cross off multiples of that number. And continue. Until prime number reaches sqrt n (here, 6). Crossed numbers: 2: all even numbers 3: 9,15,21,27,33,39 5: 25, 35 Remaining uncrossed: 2, 3, 5,7, 11,13,17,19,23,29,31,37 Point to ponder: why did I not pick up 7 ( 7 being greater than square root 40)?? Multiples of 7 lesser than 40 are 14, 21, 28, 35. Which are multiples of 2,3,4&5, all of which have already been crossed off. There you go! answered 15 Oct '15, 01:09
wooow... great explanation bro.. :) , everything is clear now.. thanks :)
(15 Oct '15, 03:32)
also you helped me in finding prime factors of a number in less time..!! so double thanks... :)
(15 Oct '15, 14:32)
@va1ts7_100 Happy to help. Happy coding :)
(15 Oct '15, 15:03)

You should print "NO" if 1) if its not a prime 2) if its a prime and not a multiple of 4k+1 But your program is not printing anything for inputs like 6,7,8,9,11,19 etc..... The mistake is here !ch=='y'. you declared ch=NULL initially, so !ch becomes 1, comparing with 'y' always results in false.... But your intension is first comparing ch==y if its false then print NO. So you should do this !(ch=='y') answered 13 Oct '15, 17:29
@lordshiva ,i corrected this mistake now , thanks , but still i am getting WA...!! and for tle , i saw people running their loop only till 2237 and not 5*10^6 . why is it so . here is the solution i am talking about. https://www.codechef.com/viewsolution/8532091
(13 Oct '15, 19:37)

Comming to the TLE issue, since you applied sieve , you can declare another array which holds all 4n+1 primes as 1 and remaining as 0 in the precomputation, since N and T are large, you can check whether its true or not without any computation for every input of n answered 13 Oct '15, 17:33

https://www.codechef.com/viewsolution/8545115 This is the link to possibly the cleanest and most clear solution explained with comments. Check it out. answered 14 Oct '15, 17:05
plz explain why you took second loop only upto 2238 and why not upto 5000000 inside the sieve function ..??
(14 Oct '15, 22:19)
is this because a number can have its prime factors not greater than than the sqaure root of the number it self..??
(14 Oct '15, 23:25)
No, a number can have a prime factor greater than it's square root. Consider the number 10. Square root of 10 is approximately 3 but the prime factors include 5 which is greater than 3. For every factor 'a' of a number N there has to be another factor 'b' such that a.b=N. If a is less than sqrt(N), then b has to be greater than sqrt(N). If a = b then a and b both are equal to sqrt(N). We use this basic property to improve our algorithm and run the loop only up to square root of N instead of N itself. Please look at my answer below for a better understanding. Happy coding :)
(15 Oct '15, 02:19)

basically the question boiled down to the fact that we have to find whether the given side can act as hypotenues or not. The prime pythagorean is always of type aa+bb where (a is even, b is odd). First try to find all those primitive and then try to find non prime solutions. reason is if aa=bb+cc then (na)(na)=(nb)(nb)+(nc)(nc) so find all such non prime since T is too large of order of 1000000 so it is better to do pre computation for(int i=1;i<2300;i++) { for(int j=i+1;j<2300;j++) { long itr=ii+jj; long k=1; if(itr<=5000000) if(arr[itr]==0) while(itrk<5000007) { arr[itrk]=1; k++; } } } so find all those and save in form of hash. for each query find in o(1)
link
This answer is marked "community wiki".
answered 16 Oct '15, 11:55

include<stdio.h>include<conio.h>void main() { int n, i, j, a[500]; printf("Enter value of n: "); scanf("%d",&n); i = 2; while (i<=n) { flag = 0; j=2; while(j<i) { if(j%a[i]==0) { flag = 1; break; } j++; } if(!flag) { if((a[i]1)%4==0) { printf("%d ",a[i]); } } i++; } getch(); } answered 16 Oct '15, 12:30
