 💯 💯 EASY & FULL EXPLANATION | JAVA | Sieve of Eratosthenes | BEATS 100% | EASY | 💯 💯
Intuition
First thing we use sieve of eratosthenes algorithm to find the prime number upto N given number
Then using the prime number we find whether the pair o
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1. First thing we use sieve of eratosthenes algorithm to find the prime number upto N given number
2. Then using the prime number we find whether the pair of number can be sumed up to target 
# Approach
<!-- Describe your approach to solving the problem. -->
# Step 1: Generate Prime Numbers Using Sieve of Eratosthenes
- Create a boolean array prime[] of size 𝑛+1
- Mark 0 and 1 as false (since they are not prime).
- **Use the Sieve of Eratosthenes:**
  - Iterate over numbers from 2 to sqrt(N)
  - If a number is prime, mark all its multiples as false (they are not prime).
  

# Step 2: Find Valid Prime Pairs Iterate over numbers from 2 to n/2
- Iterate through i 
- Compute target as taget=n−i.
- **If both i and y are marked as true** (i.e., both are prime), add the pair (x, y) to the result list.



# Complexity
- Time complexity: O(N log log N ) + O(N) = O(N log log N)
- This is becoz O(N log log N) dominates the O(N) as O(N log log N) grows slightly faster than O(N) for the larger N value as it has additional log component in it. 
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Space complexity: O(N) +O(N) = O(2N) 
- As we can boolean array of size N for sieve of Eratosthene --O(N)
- And for storing the pairs,let the number of pairs be k ,Let us take for worst case scenario k will be N ---- O(K) 
-  
<!-- Add your space complexity hereN, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> list=new ArrayList<>();
        boolean[] prime=new boolean[n+1];
        Arrays.fill(prime,true);
        prime[0]=false;
        prime[1]=false;
        for(int i=2;i<prime.length;i++){
            if(prime[i]){
                for(int j=i*2;j<prime.length;j=j+i){
                    prime[j]=false;
                }
            }
        }  
        for(int i=2;i<=n/2;i++){
            int target=n-i;
            if(prime[i] && prime[target]){
                List<Integer> arr=new ArrayList<>();
                arr.add(i);
                arr.add(target);
                list.add(arr);
            }
        }
        return list;
    }
}
```

![Screenshot 2025-04-03 213536.png](https://assets.leetcode.com/users/images/cb20c521-5ed0-4f7d-a86e-abd959c19087_1743696352.5291014.png)


['Java']