Geek Answers Handbook

How to do Millions of Computations?

My code is pasted below. When I run this program, it continues to calculate. I am using the old Turbo C ++ compiler. How long will it take to run such a program? I waited about 5 minutes, but there was no way out.

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}
+5
source share
10 answers

You do not do millions of calculations, you do trillions of them.

IsPrime will work in O (n) time, that is, it will execute 2 million instructions only to determine this singular. Performing this kind of two-minute time will take too much time.

- http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, .

+21

?

. , ~ ( ) ^ 2 (~ ) , .

, - , , , . , , , , , .

+3

, . - . :

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

2... 2 . , , . . , .

+3

gotoxy(25,25);

? 80 x 25, 25- , , , .

+3

:

TurboC++ < limits.h > , ,

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

, "" . unsigned, , "" ( 0)

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}


int goes from -2147483648 to 2147483647.
long goes from -9223372036854775808 to 9223372036854775807.

2-

unsigned ints go all the way to 4294967295
unsigned longs go all the way to 18446744073709551615
+2

/ , ""...

#define TWO_MILLION 2*1000*1000

. , -:

#define TWO_MILLION 5*1000*1000


#define FIVE_MILLION 5*1000*1000

, . , . , . MAX_NUMBER UPPER_LIMIT RANGE_TO_TEST , .

+2

, , , , . , n . ( ) , . . , ( " ", , , .

, n.

+1

.

, ( ):

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

Edit

, . , - ( )?

0

, .

, , , . , , 2 . , , .

0

, . 100 . ( 1000 10000 .)

, DOUBLE IsPrime.
, 2, i+=2 i++.

, ? ( , , )

main, . ( , 2, + = 2, 3, 3, 5, 7, 9....)

IsPrime , main , 4X. ( , 15 .)

, , sqrt(num) num

, sqrt, , 100 sqrt, .

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

PS I put this code in a C # project (minor porting). Of course, now it works on a 64-bit OS with the best compiler and 2.8 GHz processor.
He ran for less than 20 seconds.

0
source

More articles:


All Articles