Print all prime number till N

Write a program to find all prime numbers till N.

Example 1:

Input :10
Output:2 3 5 7

Approach 1: Simple 

Java

import java.util.ArrayList;
import java.util.List;
public class PrimeNumber {
    public static void main(String[] args) {
        int num = 10;
        List<Integer> allPrime = allPrimeNumber(num);
        System.out.println("All prime " + allPrime);
    }

    private static List<Integer> allPrimeNumber(int num) {
        List<Integer> allPrime = new ArrayList<Integer>();
        for (int i = 2; i <= num; i++) {
            if (checkPrime(i))
                allPrime.add(i);
        }

        return allPrime;
    }

    private static boolean checkPrime(int num) {
        for (int i = 2; i < num; i++) {
            // If a number is divisible by any number from 2 to n-1
            // then it is not a prime
            if (num % i == 0)
                return false;
        }
        return true;
    }

}
//Time Complexity:O(n^2)
//Space Complexity:O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//function to check
//given number is prime
bool isPrime(int n)
{
    for(int i=2;i<n;i++)
     {
         //if n is divisible by any number
         //other tha 1 and n then not prime
         if(n%i==0)
            return false;
     }
    return true;
}
vector<int> primeTillN(int n)
{
    vector<int> prime;
    for(int i=2;i<=n;i++)
      {
          if(isPrime(i))
             prime.push_back(i);
      }
    return prime;
}
int main()
{ 
    int num=10;
    vector<int> prime=primeTillN(num);
    for(int i=0;i<prime.size();i++)
       cout<<prime[i]<<" ";
    return 0;
}
//Time Complexity:O(n^2)
//Space Complexity:O(n)

Approach 2:Sieve of Eratosthenes

Java

import java.util.ArrayList;
import java.util.List;
public class PrimeNumber {
    public static void main(String[] args) {
        int num = 10;
        List<Integer> allPrime = primeNumberTillN(num);
        System.out.println("All prime " + allPrime);
    }


private static List<Integer> primeNumberTillN(int num) {
        List<Integer> primeN = new ArrayList<Integer>();
        boolean prime[] = new boolean[num + 1];
        // Assume all number is prime
        for (int i = 1; i <= num; i++) {
            prime[i] = true;
        }
        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i <= num; i++) {
            if (prime[i]) { // exclude non-prime number
                for (int j = i * i; j <= num; j += i)
                    prime[j] = false;
            }
        }
        for (int i = 2; i <= num; i++) {
            // add only prime number
            if (prime[i]) {
                primeN.add(i);
            }
        }
        return primeN;
    }
}
//Time Complexity:O(nloglog(n))
//Space Complexity:O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//function to find all prime 
//till N
vector<int > primeNumberTillN(int n)
{
    bool prime[n+1];
    for(int i=0;i<n;i++)
       prime[i]=true;
    prime[0]=false;
    prime[1]=false;
    for(int i=2;i<=n;i++)
     {
         if(prime[i])
          {
              for(int j=i*i;j<=n;j+=i)
                 prime[j]=false;
          }
     }
     vector<int> primeNum;
     for(int i=2;i<=n;i++)
       {
           if(prime[i])
             primeNum.push_back(i);
       }
    return primeNum;
}
int main()
{
    int num=10;
    vector<int> prime=primeNumberTillN(num);
    for(int i=0;i<prime.size();i++)
       cout<<prime[i]<<" ";
    return 0;
}
//Time Complexity:O(nloglog(n))
//Space Complexity:O(n)