Sieve of Erastothenes

Question

I'm trying to figure out how to use the sieve of eratosthenes to find the prime numbers from 1-300. I'm having trouble figuring it out, so any help would be nice! Btw, im new to programming so if you could keep it simple that would be best Below is my code (so far)

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

    #define max 301

    main()
    {
         bool is_prime[max];
         int i, int1, j, n;
         int1=sqrt(max);

  for(n=0; n<=max; n++);
  {
           is_prime[n]=TRUE; //set everything to prime
  }

  is_prime[0]=FALSE; //false = NOT prime
  is_prime[1]=FALSE;
  for(i=2; i<int1; i++); //multiply starting from 2 end at 17
  {
           for(j=i; j<=(max/i); j++); //number being multiplied by
           {
                    n=(j*i);
                    is_prime[n]==FALSE; //all multiples of i are false
           }
  }
  if (is_prime[n]=TRUE); //print all prime numbers
  {
                        printf("%d", n);
  }
  getchar();
  }

Answer 1

In order to find the prime numbers from 1-300 you have to use a technique called sieve of Eratosthenes which is the most efficient way to find the prime number list from a given range.

Here is the Code:

#include <bits/stdc++.h>
using namespace std;

const int SIZE=100010;
int status[SIZE]={1};

int sieve(){
    for(int i=0;i<=SIZE;i++)
        status[i]=1;

    for(int i=2;i<=SIZE;i++){
        if(status[i]==1){
            for(int j=2*i;j<=SIZE;j+=i){
                status[j]=0;
            }
        }
    }

}

int main(){
    sieve();
    //check from 2 to 300 which one is prime
    for(int i=2;i<300;i++){
        if(status[i]==1)
            printf("%d ",i);
    }

}

Answer 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class exp {

private int size;
private boolean[] arr;
public exp(int a){
    size = a;
    arr = new boolean[size];
}
public void initialize(){
    for(int i=2;i<size;++i)
        arr[i] = true;

    arr[0] = arr[1] = false;
}

public void precompute(){
    int i=2;
    while(i<size){
        if(arr[i]){
            for(int j=2*i; j<size; j=j+i)
                arr[j] = false;
        }
        i++;
    }
}
public String printX(int as){
    int counter = 0;
    String ans="",b = " ";
    for(int i=0; i<size ; ++i){
        if(arr[i]){
            ans += String.valueOf(i) + b;
            counter++;
        }
        if(counter == as)
            break;
    }
    return ans;
}
public static void main(String[] args) throws NumberFormatException, IOException {

    long a = System.currentTimeMillis();
    exp e = new exp(50000);
    e.initialize();
    e.precompute();
    long b = System.currentTimeMillis();

    //System.out.println(b-a);
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    int N;
    for(int i=0;i<t;++i){
        N = Integer.parseInt(br.readLine());
        if(N == 1)
            System.out.println("1");
        else
            System.out.println(e.printX(N));
    }
}

}

Answer 3

Here is a sample implementation in c++:

void sieve_of_eratosthenes(int n)
{
    bool *sieve = new bool[n+1];

    // Initialize
    sieve[0]=false;
    sieve[1]=false;
    sieve[2]=true;

    for(int i=3;i<n+1;++i)
        sieve[i]=true;

    // Actual sieve
    for(int i=1; i<n+1; ++i)
        if(sieve[i]==true)
            for(int j=2;j*i<n+1;++j)
                sieve[j*i]=false;

    // Output
    cout << "Prime numbers are: " <<endl;
    for(int i=0;i<n+1;++i)
        if (sieve[i])
            cout << i <<endl;

    delete [] sieve;
}

int main()
{
    int n = 70;
    sieve_of_eratosthenes(n);
}

Answer 4

You can have a look at the implementation here.

Sieve implementation:

bool arr[1000001];
int main()
{
    arr[0]=arr[1]=1;
    for(int i=4;i<1000001;i+=2)
        arr[i]=1;
    for(int i=3;i<1000001;i+=2)
    {
        if(!arr[i])
            for(int j=2;i*j<1000001;j++)
            {
                arr[i*j]=1;
            }
    }
    return 0;
}

And there is a blog written on Prime Numbers link.

Answer 5

Be inappropriate semicolon except that it has been already pointed out. E.g. Is not executed when the block such as the following intended

for(n=0; n<=max; n++);
{
....
}

fix like this

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

#define max 301

int main(){
    bool is_prime[max];
    int i, int1, j, n;
    int1=sqrt(max);//17

    for(n=0; n<max; ++n){
        is_prime[n]=true;
    }

    is_prime[0]=false; //false = NOT prime
    is_prime[1]=false;

    for(i=2; i<int1; i++){
        if(is_prime[i])
            for(j=i+i; j<max; j+=i){
                is_prime[j]=false;
            }
    }
    for(n=2;n<max;++n){
        if(is_prime[n]==true)
            printf("%d ", n);
    }
    return 0;
}

---

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

#define max 300+1

int main(void){
    static is_prime[max]={0};
    int i, int1, n;
    int *p;

    int1=sqrt(max);
    is_prime[2] = 1;
    p = &is_prime[3];
    for(n=3; n<max; n+=2, p+=2)
        *p = 1;

    for(n=3; n<int1; n+=2)
        if(is_prime[n])
            for(i=n+n; i<max; i+=n)
                is_prime[i] = 0;
    for(n=2;n<max;++n)
        if(is_prime[n])
            printf("%d ", n);
    return 0;
}

Answer 6

     class Program {

            static void Main(string[] args) {
                const byte disqualified = 1;
                const byte isprime = 2;


                int max = 300;

                byte[] numbers = new byte[max + 1];

                for (int outerIndex = 2; outerIndex < max + 1; outerIndex++) {
                    if (numbers[outerIndex] != disqualified) {
                        numbers[outerIndex] = isprime;
                        for (int innerIndex = outerIndex * 2; innerIndex < max + 1; innerIndex += outerIndex) {
                            numbers[innerIndex] = disqualified;
                        }
                    }
                }

                for (int i = 2; i < numbers.Length; i++) {
                    if (numbers[i] == isprime) {
                        Console.WriteLine("{0} is a prime number, thanks E my toga clad nerd buddy", i);
                    }
                }

                Console.ReadKey();
            }
        }

yes, C# example - but near enough to convert

Results in: