3 Replies - 1749 Views - Last Post: 24 January 2012 - 02:39 PM Rate Topic: -----

#1 Louisda16th   User is offline

  • dream.in.assembly.code
  • member icon

Reputation: 15
  • View blog
  • Posts: 1,967
  • Joined: 03-August 06

Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 12 August 2006 - 01:19 AM

Description: compile, build n runThis program uses a simple method developed by Eratosthenes(Greek mathematician). Basically u select a number an strike of all its multiplies. then u go to the next number n so on till u reach the end. What ure left with r prime numbers.
/* Finding Prime Numbers Using The Sieve Of Eratosthenes*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int *num;
  int i, j, s_size, prime;


  printf("Enter sieve size:n");
  scanf("%0d", &s_size);
  num = malloc(s_size*sizeof(int));

  for(i = 0; i < s_size; i++)
       num[i]=i+1;
  
  for(i = 1; i < s_size; i++)
  {
    //Select the next non-zero number as the next prime.
    if(num[i] != 0)
      prime = num[i];
    else
      continue;

    //Set all numbers occuring in steps of the selected prime to 0.
    j = prime+prime;

    while(j <= s_size)
    {
      num[j-1] = 0;          
      j += prime;
    }
        
  }

  
  for(i=0;i<s_size;i++)
  {
    if(num[i]!=0)                    /*Print all non zero numbers (prime numbers)*/
       printf("%dn",num[i]);
  }
  return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Finding Prime Numbers Using The Sieve Of Eratosthenes

#2 NSLogan   User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 24-March 09

Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 24 March 2009 - 01:01 PM

poor scalability
Was This Post Helpful? 0
  • +
  • -

#3 kame.akbare   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 20-August 10

Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 20 August 2010 - 03:33 PM

I want program : find prime large numbers latest numbers 150 digit mail: [email protected]
Was This Post Helpful? 0
  • +
  • -

#4 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Finding Prime Numbers Using The Sieve Of Eratosthenes

Posted 24 January 2012 - 02:39 PM

This snippet does not actually implement sieve of Eratosthenes. When you find a prime you should take steps of prime through the list and remove exactly those elements. What you do is take steps of one through a list and do trial division.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1