Threaded Mode | Linear Mode

***drdebcol*** · 04-04-2010, 04:22 AM

I made a small example of sum of prime numbers.
More about prime numbers you have here :
http://www.pro9ramming.com/program-for-f...-t-60.html
So basically if you have sequence of primes :

Code:

2,3,5,7,11 . . .

Sum of first 5 prime numbers is 28 !
So here is the code in Turbo Pascal for Windows :

Code:

program sum_of_prime_numbers;

uses wincrt;

var

i,n,k:integer;

s:longint;

function prime(a:integer):boolean;

var

  i:integer;

  b:boolean;

begin

  if a=2 then

    prime:=true

  else

    if a mod 2 = 0 then

      prime:=false

    else

     begin

      b:=true;

      for i:=2 to trunc(sqrt(a))+1 do

       if (a mod i = 0) and (b=true) then

        b:=false;

       if b=true then

         prime:=true

       else

         prime:=false;

     end;   

end;

begin

 readln(n);

s:=0;

k:=0;

for i:=2 to n do

  if prime(i) then

    begin

     s:=s+i;

     k:=k+1;

    end;

  writeln('Sum of first ',k,' prime numbers is : ',s);

end.

codecaine · 04-04-2010, 12:17 PM

Here is a link to sum of primes I did a while back http://www.pro9ramming.com/prime-sum-cha...t-796.html

***drdebcol*** · 04-04-2010, 09:11 PM

(04-04-2010 12:17 PM)codecaine Wrote: Here is a link to sum of primes I did a while back http://www.pro9ramming.com/prime-sum-cha...t-796.html

Yeah, that is below 5000 !
Very good !

TheBear · 04-23-2010, 06:00 AM

Here is the same code done in C:

Code:

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

int prime (int n)

{

    int i, k;

    if (n==2)

    return n;

    else if (n%2==0)

    return 0;

    else 

    for(i=2; i<=floor((sqrt(n))+1); i++)

    {

    if (n%i!=0)

    return n;

}

}

main()

{

      int n, i;

       while (2)

          {

      do

      {

          printf("Number to test= ");

          scanf("%d", &n);

          }

          while (n<1);

                if (prime(n))

                printf("%d is a prime number.", n);

                else 

                printf("%d is not a prime number", n);

                printf("\n \n");

                }

          system("pause");

          }

***drdebcol*** · 04-23-2010, 07:21 AM

Very good TheBear. That is for validation if number is prime.
But few optimizations. When you look into definition of prime numbers on Wikipedia : Prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself. As you can see primes are natural numbers that means that they can be described as unsigned integers.
So instead of every "int" in program you could use "unsigned int".
In function prime() you could declare it as short because if you declare it as int that is memory waste. Because bool is not defined in C (it is in C++) you need to use integer types, but memory is important and short uses less than int.
Also in this part :

Code:

if (n==2)

    return n;

You returned n, you could return "1", because that means that 2 is a prime, because "1" is true.
I like this line :

Code:

for(i=2; i<=floor((sqrt(n))+1); i++)

You used floor() that is trunc() in Pascal, and it is opposite than ceil().
But this line has one mistake. You already checked if 2 is divisor of that
number, so loop starts with 3, like this :

Code:

for(i=3; i<=floor((sqrt(n)))+1; i++)

And this code would return that 1 is a prime number which is not true according to definition.
All in all, it's okay, just a few corrections.
We respect work !

TheBear · 04-23-2010, 07:59 PM

Thank you for the corrections.

Optimization is something i have yet to learn.

***drdebcol*** · 04-23-2010, 10:02 PM

(04-23-2010 07:59 PM)TheBear Wrote: Thank you for the corrections.

Optimization is something i have yet to learn.

Yeah that is positive. Basically, just think generally about the algorithm and try to find a way to optimize it by making loops doing smaller amount of iterations, or maybe calling some functions less. You can do it by using compiler's faster functions etc. If you find a way that is totally different than bruteforce, even optimized bruteforce, that can do things by certain formula or with very small number of iterations, that is dynamic programming.
BTW in this line :

Code:

for(i=2; i<=floor((sqrt(n))+1); i++)

You can just skip all even numbers and start from 3 (i already mentioned that in previous post). If you check divisibility with even numbers, it is obvious that you are doing unnecessary iterations, because you already checked divisibility with 2 (only even prime number).
So this line should look like this:

Code:

for(i=3; i<=floor(sqrt(n))+1; i+=2)

As you can see instead of "i++" we use "i+=2".

TheBear · 04-23-2010, 10:51 PM

Even I know that after today's class Big Grin