ACM (UVa) : 543


#include <stdio.h>
#include <math.h>

int main ()
{
    bool prime [1000005];
    int length = (int) sqrt (1000005);

    for ( int i = 0; i < 1000005; i++ )
        prime [i] = true;

    for ( int i = 2; i <= length; i++ ) {
        for ( int j = i * 2; j < 1000005; j += i )
            prime [j] = false;
    }

    int n;

    while ( scanf ("%d", &n) && n ) {

        bool flag = true;

        int i = 3;

        while ( i <= n - i && flag ) {
            if ( prime [n - i] && prime [i]) {
                printf ("%d = %d + %d\n", n, i, n - i);
                flag = false;
            }

            i += 2;
        }
    }

    return 0;
}

One thought on “ACM (UVa) : 543

  1. hi,
    it would be faster if instead of
    int main ()
    {
    bool prime [1000005];
    int length = (int) sqrt (1000005);

    for ( int i = 0; i < 1000005; i++ )
    prime [i] = true;

    for ( int i = 2; i <= length; i++ ) {
    for ( int j = i * 2; j < 1000005; j += i )
    prime [j] = false;
    }
    You write
    int main ()
    {
    bool prime [1000005];
    int length = (int) sqrt (1000005);

    for ( int i = 0; i < 1000005; i++ )
    prime [i] = true;

    for ( int i = 2; i <= length; i++ ) {
    if(prime[i] == true) /*THIS IS THE MODIFICATION*/
    for ( int j = i*2; j < 1000005; j += i )
    prime [j] = false;
    }
    Your code's execution time is 0.065 while by the modification it is 0.055.
    Btw thanks for your code,I learned the faster way to generate primes,new to coding :).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s