CodeExplorer Posted April 22, 2018 Share Posted April 22, 2018 Prime numbers Quote For all the primes in the interval [400, 900], find for each number the amount of iterations required to reach 1, as if the number was used to start the sequence in the Collatz conjecture. The solution to the challenge is the sum of all the resulting numbers. A prime is a number that is only divisible by 1 or itself. For example, 13 is a prime number.The Collatz conjecture concerns a sequence that starts with any positive number n. Each next term is obtained using the following rules: If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. The conjecture states that repeating this process will result in the sequence converging to the number 1. For example the number 13 requires 9 iterations to reach 1, namely: [40, 20, 10, 5, 16, 8, 4, 2, 1]. Solution: https://text-share.com/view/03a0d1ed Link to comment

skylark Posted May 2, 2018 Share Posted May 2, 2018 In the block of checking whether it's a non-prime number, in the loop line, for (int j=2; j<=n/2; j++) if the condition is kept like ( j * j <= n) or ( int len = sqrt(n+1); j <= len) then some more efficiency can be achieved, as some unnecessary loops will be skipped. 1 Link to comment

CodeExplorer Posted May 2, 2018 Author Share Posted May 2, 2018 Thanks for info. The code: Quote int flag2 = 0; for (int j=2; j*j<=n; j++) { steps1++; // condition for nonprime number if(n%j==0) { flag2=1; break; } } works ok and is fast! Link to comment

NOP Posted May 2, 2018 Share Posted May 2, 2018 You can also hard code 2 as a prime and then start your loop at 3 and increment by 2 so you skip checking all the even numbers, cutting your steps in half 😉 1 Link to comment

CodeExplorer Posted May 3, 2018 Author Share Posted May 3, 2018 (edited) Factorize online: https://www.numberempire.com/numberfactorizer.php Upgraded to v2 according to skylark simplification: https://text-share.com/view/a1c3b868 Edited May 3, 2018 by CodeExplorer Link to comment

CodeExplorer Posted May 3, 2018 Author Share Posted May 3, 2018 (edited) Even number solution: https://text-share.com/view/e6f301fb#L5 skylark solution doesn't work for that! Edited May 3, 2018 by CodeExplorer Link to comment

skylark Posted May 3, 2018 Share Posted May 3, 2018 2 hours ago, CodeExplorer said: Even number solution: https://text-share.com/view/e6f301fb#L5 skylark solution doesn't work for that! Um, I am kinda lost, where are you getting these problems from? Was this problem (and also the 3n+1 problem) posted somewhere in this forum? Give link to the thread please, or are you just solving random problems from random online judges? Anyway, from the output, I see you are printing the divisors for all non-prime numbers from 0 to 98. Now, question is, why j*j <= n doesn't work in your solution, but j <= n/2 does, actually, for a composite number n, if you divide it by a number j, if (n % j == 0) then both j and n/j becomes it's divisor. Whenever you encountered a (n%j == 0), you have only printed j, skipped the n/j. If j is less than root(n), then n/j will obviously be greater that root(n). Since you didn't print n/j first, you had to loop upto n/2. For example, if you factorize 64, 2 * 32 4 * 16 8 * 8 when we found (64%2==0), if we took 2 and 32 both, we wouldn't have to check for 32 in later stage. we could have done this iterating from 2 to root(64) only. There is a classical problem about this kind of iteration, named k-th divisor. you can also check it. And this might explain better https://stackoverflow.com/questions/26753839/efficiently-getting-all-divisors-of-a-given-number Link to comment

CodeExplorer Posted May 3, 2018 Author Share Posted May 3, 2018 Even number solution is my own problem solved. The solution you posted seems much better. The original problem is posted from a forum, don't know if I should write the name of forum! Link to comment

CodeExplorer Posted May 3, 2018 Author Share Posted May 3, 2018 (edited) Finded a good solution (C) from skylark link: int main(int argc, char *argv[]) { int num = 75; int square_root = (int) sqrt(num) + 1; for (int i = 1; i < square_root; i++) { if (num%i==0) { if (i*i==num) printf("%d \r\n", i); else printf("%d %d \r\n" , i, num/i); } } return 0; } Edited May 3, 2018 by CodeExplorer Link to comment

skylark Posted May 3, 2018 Share Posted May 3, 2018 1 hour ago, CodeExplorer said: The original problem is posted from a forum, don't know if I should write the name of forum! Not necessary to write the name of the forum though, in case it goes against any privacy or rules. Just I never found any problem solving / competitive programming related thread here, so wondered if I missed any such post. Since this is an RCE focused forum, I don't know if competitive programming related threads are appreciated here (as there is no subforum for this kind of threads and discussion). And about the original problem, Collatz conjecture is a widely known problem though, uva-100 problem is about that. Since you have already solved a more complicated version of it, you can check if it passed all test cases. uva link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36 Link to comment

NOP Posted May 3, 2018 Share Posted May 3, 2018 1 hour ago, skylark said: I don't know if competitive programming related threads are appreciated here (as there is no subforum for this kind of threads and discussion). I would say the sub forum it's in qualifies along with the replys/tips? Quote Programming and Coding Programming and coding tips, help and solutions... Link to comment

skylark Posted May 3, 2018 Share Posted May 3, 2018 (edited) 13 minutes ago, NOP said: I would say the sub forum it's in qualifies along with the replys/tips? Since almost no one talks about problem solving, I guessed this sub-forum could be for talking about coding loaders, crackers, unpackers or other misc app develop related questions. Problem solving area is huge, there are tons of forums related to competitive programming only, so it wouldn't be surprising to me if admins intended to keep this forum more clean and focused on rce by putting some restriction over problem solving stuff discussion. Anyway, I was wrong. Edited May 3, 2018 by skylark Link to comment

CodeExplorer Posted May 3, 2018 Author Share Posted May 3, 2018 The subforum is good! Also I don't think Ted ever put high restrictions on this forum. But yeah If you ever make crack requests on this board you will get an instant ban! Link to comment

atom0s Posted May 3, 2018 Share Posted May 3, 2018 https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/ There's a bunch of different methods of generating primes. Link to comment

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now