sieve of eratosthenes

1//sieve of eratosthenes or prime of sieve
2#include<iostream>
3#include<math.h>
4using namespace std;
5void primeofsieve(long long int n)
6{
7	long long int arr[n]={};
8	for(int i=2;i<=sqrt(n);i++)
9	{
10		for(long long int j=i*i;j<=n;j+=i)
11			arr[j]=1;
12	}
13	for(long long int i=2;i<=n;i++)
14	{
15	    if(arr[i]==0)
16	    	cout<<i<<" ";
17	}
18
19
20}
21int main()
22{
23
24	#ifdef _DEBUG
25	freopen("input.txt", "r", stdin);
26	freopen("output.txt", "w", stdout);
27    #endif
28	long long int n;
29	cin>>n;
30	cout<<"PRIME NUMBERs ARE : ";
31	primeofsieve(n);
32	return 0;
33}

1
2find primes up to N
3For all numbers a : from 2 to sqrt(n)
4     IF a is unmarked THEN
5         a is prime
6         For all multiples of a (a < n)
7             mark multiples of as composite
8All unmarked nummbers are prime!
9

1function solution(n) {
2   const numArr = new Array(n + 1);
3   numArr.fill(true);
4	// from 1 to n, if number is NOT a prime, change true to false in numArr
5   numArr[0] = numArr[1] = false;
6   for (let i = 2; i <= Math.sqrt(n); i++) {
7      for (let j = 2; i * j <= n; j++) {
8          numArr[i * j] = false;
9      }
10   }
11  	// find number of true(number of prime) by filtering true boolean
12   return numArr.filter(Boolean).length;
13}
14
15

1function solution(n) {
2   const numArr = new Array(n + 1);
3   numArr.fill(true);
4   numArr[0] = numArr[1] = false;
5   for (let i = 2; i <= Math.sqrt(n); i++) {
6      for (let j = 2; i * j <= n; j++) {
7          numArr[i * j] = false;
8      }
9   }
10   return numArr.filter(Boolean).length;
11}
12
13

1
2import java.util.Scanner;
3
4public class BooleanPrimes
5{
6
7    public static int counter = 0 ;
8    public static void main(String[] argh)
9    {
10        Scanner scanner = new Scanner(System.in);
11        System.out.println("Enter a number: ");
12        int size = scanner.nextInt();
13        boolean[] boolArray = new boolean[size+1];
14        printArray( generateBoolArray(boolArray,size+1),size);
15    }
16
17    public static boolean[] generateBoolArray(boolean[] boolArr, int size) // initializing boolean array with true values
18    {
19        for (int i = 2; i < size; ++i)
20        {
21            boolArr[i] = true;
22        }
23        return chickIfIndexPrime(boolArr, boolArr.length,size);
24    }
25
26    public static boolean[] chickIfIndexPrime(boolean[] arrIsPrime, int input, int size)
27    {
28        int start = 2;
29        while (start*start <= input) // first+second loop checking if start is prime
30        {
31            int i = 2;
32            boolean isprime = true;
33            while(i*i < start && isprime ) // second loop
34            {
35                if(start%i == 0)
36                {
37                    isprime = false;
38                }
39                ++i;
40            }
41            if(isprime==true)
42            {
43                for(int j=4; j<arrIsPrime.length;++j) // third loop checking if the index of the array is prime
44                {
45
46                    if(j%start ==0 )
47                    {
48                        if(j == start)
49                        { 
50                            ++j;
51                            if(j >=arrIsPrime.length)
52                            {
53                                break;
54                            }
55                        }
56                        arrIsPrime[j]=false;
57                    }
58                }
59            }
60            ++start;
61
62        }
63        return arrIsPrime;
64    }
65
66
67
68    public static void printArray(boolean[] arr ,int size){
69        System.out.println("The prime numbers from 2 till "+(size));
70        int i=0,j = 0 ;
71        while(i<arr.length){
72            if ( arr[i] == true ) {
73                System.out.print(i+" ");
74                ++counter;
75
76            }
77            ++i;
78        }
79
80        System.out.println();
81        System.out.println("\nIn total there is "+counter+" prime numbers");
82
83    }
84
85}
86
87
88
89
90
91
92
93
94
95
96