Prime numbers solution

[CodeExplorer]

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

[skylark]

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.

[CodeExplorer]

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!
 

[NOP]

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 😉

[CodeExplorer]

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

[CodeExplorer]

Even number solution:
https://text-share.com/view/e6f301fb#L5

skylark solution doesn't work for that!
 

Edited May 3, 2018 by CodeExplorer

[skylark]

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

[CodeExplorer]

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!
 

[CodeExplorer]

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

[skylark]

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

[NOP]

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

 

 

[skylark]

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

[CodeExplorer]

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!

 

[atom0s]

https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/

There's a bunch of different methods of generating primes.