sieve of eratosthenes java

Question

I am trying to write a program that implements the sieve of eratosthenes. I can get it from 2 to any given end number but the assignment we are working on asks that we input the starting value. I am completely stuck. I've tried many different codes but it keeps giving me weird answers.

My start is the starting value and end is the ending value. I basically want to find the prime of this range. Thank you!!!

    public static void sieve(int start, int end) {
    int size=(end-start)+1;
    boolean result[]=new boolean[size];
    int prime[]=new int[size];

    for(int i=0; i<size; i++) {
        prime[i]=start+i;
    }


    for(int i=0; i<size; i++) { //every number in result is true
        result[i]=true;
    }

    for(int p=2; p*p <size; p++) {
        if(result[p]==true) {
            for(int i=p*2; i<size; i +=p) {
                result[i]=false;
            }
        }

        for(int i=2; i<size; i++) {
            if(result[i]==true) {
                System.out.print(prime[i] + " ");

            }
        }
    }
}

Check this implementation https://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html — hovanessyan, Feb 11 '18 at 10:03
You are looking for a _segmented_ Sieve of Eratosthenes. See my answer at Stack Overflow [here](https://stackoverflow.com/a/10249801/448810). — user448810, Feb 12 '18 at 13:56
use the [*offset*](https://stackoverflow.com/a/19641049/849891) sieve of Eratosthenes. (a segmented sieve finds them all, in segments; but you only need two segments, with a potentially huge gap in between, resulting in similarly huge time savings) — Will Ness, Oct 30 '21 at 14:00

score 0 · Accepted Answer · answered Feb 11 '18 at 10:26

0

The Sieve of Eratosthenes works by marking as not prime the multiples of each prime, starting with the first prime number, 2.

Therefore, even if you are required to find the primes between start and end, you still have to find all the primes between 2 and end. After you do that, just output the primes within the requested range.

answered Feb 11 '18 at 10:26

Eran

387,369
54
702
768

incorrect. it is _enough_ to know the primes in just `[2 .. sqrt(end)]` range, to also find the primes in `[start .. end]` range. – Will Ness Oct 30 '21 at 14:01

score 0 · Answer 2 · edited Oct 30 '21 at 11:43

public class To_find_a_prime_number_using_sieve_of_Eratosthenes { 
    public static void main(String args[]){

        int end_number;
        int arr[];
        arr=new int[100];
        Scanner S=new Scanner(System.in); 
        System.out.println("enter the end number which you want to print he prime number"); 
        end_number=S.nextInt(); 
        //adding natural numbers in the array
        for(int i=0;i<end_number;i++)
        {
            arr[i]=i;
        }
        for(int k=2;k<end_number;k++)
        {

            for(int l=2;l<end_number;l++)
            {
                if(arr[k]*l>end_number)
                { 
                    break; 
                } 
                else {
                    arr[arr[k]*l]=0;
                }

            }

        }

        for(int j=1;j<end_number;j++)
        {
            if(arr[j]!=0 && arr[j]!=1)
            {
                System.out.println(arr[j]); 
            } 
        }
    }
}

While this code may solve the question, [including an explanation](//meta.stackexchange.com/q/114762) of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please [edit] your answer to add explanations and give an indication of what limitations and assumptions apply. — Suraj Rao, Oct 30 '21 at 11:43

sieve of eratosthenes java

2 Answers2