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 - https://www.codechef.com/viewsolution/8536013

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’)

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

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.


This is the link to possibly the cleanest and most clear solution explained with comments.
Check it out.
[1]: https://www.codechef.com/viewsolution/8545115

@va1ts7_100 2238 is approx sqrt(5000000)

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!

1 Like

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;
so find all those and save in form of hash. for each query find in o(1)

void main()
int n, i, j, a[500];
printf(“Enter value of n: “);
i = 2;
while (i<=n)
flag = 0;
flag = 1;

printf("%d ",a*);

@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

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

thanks @rjohari:slight_smile: , i understood the solution finally …!

is this because a number can have its prime factors not greater than than the sqaure root of the number it self…??

u r welcome :slight_smile:

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 :slight_smile:

wooow… great explanation bro… :slight_smile: , everything is clear now… thanks :slight_smile:

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

Happy to help. Happy coding :slight_smile: