You are not logged in. Please login at to post your questions!


[closed] equilateral triangle question in october challenge

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. my solution -

asked 13 Oct '15, 15:13

va1ts7_100's gravatar image

accept rate: 11%

edited 26 Oct '15, 14:11

admin's gravatar image

0★admin ♦♦

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

1) use prime sieve for finding all numbers of the form $4k+1$ since $N$ is very large here (5*106).
2) store all these numbers in an array,
3) mark all the multiple of these numbers,

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

rjohari23's gravatar image

accept rate: 14%

thanks @rjohari... :) , i understood the solution finally ..!

(14 Oct '15, 22:25) va1ts7_1003★

u r welcome :)

(14 Oct '15, 23:39) rjohari233★

@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

raunak_parijat's gravatar image

accept rate: 0%

wooow... great explanation bro.. :) , everything is clear now.. thanks :)

(15 Oct '15, 03:32) va1ts7_1003★

also you helped me in finding prime factors of a number in less time..!! so double thanks... :)

(15 Oct '15, 14:32) va1ts7_1003★

@va1ts7_100 Happy to help. Happy coding :)

(15 Oct '15, 15:03) raunak_parijat4★

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

lordshiva1996's gravatar image

accept rate: 20%

@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.

(13 Oct '15, 19:37) va1ts7_1003★

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

lordshiva1996's gravatar image

accept rate: 20% This is the link to possibly the cleanest and most clear solution explained with comments. Check it out.


answered 14 Oct '15, 17:05

raunak_parijat's gravatar image

accept rate: 0%

plz explain why you took second loop only upto 2238 and why not upto 5000000 inside the sieve function ..??

(14 Oct '15, 22:19) va1ts7_1003★

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) va1ts7_1003★

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) raunak_parijat4★

@va1ts7_100 2238 is approx sqrt(5000000)


answered 14 Oct '15, 22:54

bhishma's gravatar image

accept rate: 11%

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)

This answer is marked "community wiki".

answered 16 Oct '15, 11:55

pola7's gravatar image

accept rate: 0%



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

rajat_kumar's gravatar image

accept rate: 0%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 13 Oct '15, 15:13

question was seen: 1,738 times

last updated: 26 Oct '15, 14:11