You are not logged in. Please login at www.codechef.com 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. https://www.codechef.com/OCT15/problems/ADTRI/ my solution - https://www.codechef.com/viewsolution/8536013

asked 13 Oct '15, 15:13

va1ts7_100's gravatar image

3★va1ts7_100
4721732
accept rate: 11%

edited 26 Oct '15, 14:11

admin's gravatar image

0★admin ♦♦
19.8k350498541

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

link

answered 14 Oct '15, 15:23

rjohari23's gravatar image

3★rjohari23
779214
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!

link

answered 15 Oct '15, 01:09

raunak_parijat's gravatar image

4★raunak_parijat
8726
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')

link

answered 13 Oct '15, 17:29

lordshiva1996's gravatar image

5★lordshiva1996
13615
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. https://www.codechef.com/viewsolution/8532091

(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

link

answered 13 Oct '15, 17:33

lordshiva1996's gravatar image

5★lordshiva1996
13615
accept rate: 20%

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

link

answered 14 Oct '15, 17:05

raunak_parijat's gravatar image

4★raunak_parijat
8726
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)

link

answered 14 Oct '15, 22:54

bhishma's gravatar image

4★bhishma
2977
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)

link
This answer is marked "community wiki".

answered 16 Oct '15, 11:55

pola7's gravatar image

3★pola7
1
accept rate: 0%

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(); }

link

answered 16 Oct '15, 12:30

rajat_kumar's gravatar image

0★rajat_kumar
1
accept rate: 0%

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×301
×4

question asked: 13 Oct '15, 15:13

question was seen: 1,738 times

last updated: 26 Oct '15, 14:11