Jump to content
Tuts 4 You
Sign in to follow this  
CodeExplorer

Prime numbers solution

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

  • Thanks 1

Share this post


Link to post
Share on other sites
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!
 

Share this post


Link to post
Share on other sites
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 😉

  • Confused 1

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!
 

Share this post


Link to post
Share on other sites
CodeExplorer
Posted (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 by CodeExplorer (see edit history)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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...

 

 

Share this post


Link to post
Share on other sites
skylark
Posted (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 by skylark (see edit history)

Share this post


Link to post
Share on other sites
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!

 

Share this post


Link to post
Share on other sites

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
Sign in to follow this  

×