[BUG] Optimise the Steve of eratosthenes Algorithm

[Swarga-codes]

Description

I was going through the code, that is, the SIEVE OF ERASTOSTHENES Algo and found it was somewhere between 80 82 lines, the code was quite long, can I improve it by reducing the size of the code?

Steps to reproduce

No response

Excepted behavior

The code is performing as expected but it was quite large and lengthy, I would like to shorten the code.

Screenshots

Additional context

No response

[sanjug-sonowal]

i have optimised the algorithm

[Swarga-codes]

I mean to say that the number of lines is quite large I can reduce it to half the size of the current algorithm. @siriak can you assign me this?

[yanurag1414]

Code was good but i can reduce lines and optimise it.@siriak can you assign me this.

[siriak]

Please open PRs with the changes you want to make

[rohan472000]

@siriak , opened a PR with some changes, please review and suggest if its need any change.

[dhanmeetsingh]

Hey there!

So, here are some steps that can be taken to improve the existing code for Sieve of Eratosthenes algorithm in an informal way:

We can replace the 'Type' enum with a boolean array to store the prime numbers' status. This will reduce the memory used and make the code simpler to understand.
Instead of calculating the square root of the input number in each iteration, we can calculate it once before the loop starts and store it in a variable. This will make the code run faster.
We can combine the two for loops that write the primes to the result array and calculate the count of primes into one loop. This will make the code more efficient.
Instead of using the 'filter' method to count the number of prime numbers, we can use a variable to count them as we mark each prime number. This will save us from iterating through the array again just to count the number of primes.
Hope this helps!

`
public class SieveOfEratosthenes {

public static int[] findPrimesTill(int n) {
    boolean[] primes = new boolean[n + 1];
    Arrays.fill(primes, true);
    primes[0] = primes[1] = false;

    int cap = (int) Math.sqrt(n);
    for (int i = 2; i <= cap; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }

    int[] result = new int[n + 1];
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (primes[i]) {
            result[count++] = i;
        }
    }
    return Arrays.copyOf(result, count);
}

public static void main(String[] args) {
    int n = 100;
    System.out.println("Searching for all primes from zero to " + n);
    int[] primes = findPrimesTill(n);
    System.out.println("Found: " + Arrays.toString(primes));
}

}
`

[pengxiaoshuai]

powerful

[Aman254]

Sure! Why not Can you please Assign Me ? A Request

[Jaiyadav88]

It can be optimized ,which reduces the length of the code ,Assign it to me?

[rohan472000]

@siriak kindly look in #4149 for this issue.

[siriak]

Fixed in #4149