Find count of Almost Prime numbers from 1 to N

0 0 8 minutes read

Given a number N. Find number of almost primes from 1 to $n$ . A number is called almost if it has exactly two distinct prime factors.
Note: The numbers can have any number of non-prime factors but should have exactly two prime factors.
Examples:

Input : N = 10
Output : 2
Explanation : 6, 10 are such numbers.

Input : N = 21
Output : 8

An efficient solution is to find prime numbers using Sieve of Eratosthenes. And find distinct prime factors count for numbers less than N.
Please Refer: Almost Prime Numbers
Below is the implementation of the above approach:

C++

// CPP program to count almost prime numbers
// from 1 to n
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[N];
 
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
    prime[1] = false;
 
    for (int p = 2; p * p < N; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i < N; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to count almost prime numbers
// from 1 to n
int almostPrimes(int n)
{
    // to store required answer
    int ans = 0;
 
    // 6 is first almost prime number
    for (int i = 6; i <= n; i++) {
        // to count prime factors
        int c = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                // if it is perfect square
                if (j * j == i) {
                    if (prime[j])
                        c++;
                }
                else {
                    if (prime[j])
                        c++;
                    if (prime[i / j])
                        c++;
                }
            }
        }
 
        // if I is almost prime number
        if (c == 2)
            ans++;
    }
    return ans;
}
 
// Driver code
int main()
{
    SieveOfEratosthenes();
    int n = 21;
 
    cout << almostPrimes(n);
 
    return 0;
}

C

// C program to count almost prime numbers
// from 1 to n
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define N 100005
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[N];
 
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
    prime[1] = false;
 
    for (int p = 2; p * p < N; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i < N; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to count almost prime numbers
// from 1 to n
int almostPrimes(int n)
{
    // to store required answer
    int ans = 0;
 
    // 6 is first almost prime number
    for (int i = 6; i <= n; i++) {
        // to count prime factors
        int c = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                // if it is perfect square
                if (j * j == i) {
                    if (prime[j])
                        c++;
                }
                else {
                    if (prime[j])
                        c++;
                    if (prime[i / j])
                        c++;
                }
            }
        }
 
        // if I is almost prime number
        if (c == 2)
            ans++;
    }
    return ans;
}
 
// Driver code
int main()
{
    SieveOfEratosthenes();
    int n = 21;
 
    printf("%d",almostPrimes(n));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

Java

// Java program to count almost prime numbers
// from 1 to n
 
import java.io.*;
 
class GFG {
 
static int N = 100005;
 
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
static boolean prime[] = new boolean[N];
static void SieveOfEratosthenes()
{
    for(int i=0;i<N;i++)
    prime[i] =true;
    prime[1] = false;
 
    for (int p = 2; p * p < N; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i < N; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to count almost prime numbers
// from 1 to n
static int almostPrimes(int n)
{
    // to store required answer
    int ans = 0;
 
    // 6 is first almost prime number
    for (int i = 6; i <= n; i++) {
        // to count prime factors
        int c = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                // if it is perfect square
                if (j * j == i) {
                    if (prime[j])
                        c++;
                }
                else {
                    if (prime[j])
                        c++;
                    if (prime[i / j])
                        c++;
                }
            }
        }
 
        // if I is almost prime number
        if (c == 2)
            ans++;
    }
    return ans;
}
 
// Driver code
 
    public static void main (String[] args) {
        SieveOfEratosthenes();
    int n = 21;
 
    System.out.println( almostPrimes(n));
    }
}
//This code is contributed by inder_verma..

Python 3

# Python 3 program to count almost 
# prime numbers 
# from 1 to n 
 
# from math import everything
from math import *
 
N = 100005
 
# Create a boolean array "prime[0..n]"
# and initialize all entries it as true. 
# A value in prime[i] will 
# finally be false if i is Not a prime, else true. 
prime = [True] * N
 
def SieveOfEratosthenes() :
 
    prime[1] = False
 
    for p in range(2, int(sqrt(N))) :
 
        # If prime[p] is not changed, then 
        # it is a prime 
        if prime[p] == True :
 
            # Update all multiples of p 
            for i in range(2*p, N, p) :
                prime[i] = False
 
 
# Function to count almost prime numbers 
# from 1 to n 
def almostPrimes(n) :
 
    # to store required answer
    ans = 0
 
    # 6 is first almost prime number 
    for i in range(6, n + 1) :
 
        # to count prime factors 
        c = 0
        for j in range(2, int(sqrt(i)) + 1) :
 
            # if it is perfect square
            if i % j == 0 :
 
                if j * j == i :
                    if prime[j] :
                        c += 1
                else :
                    if prime[j] :
                        c += 1
                    if prime[i // j] :
                        c += 1
 
        # if I is almost prime number 
        if c == 2 :
            ans += 1
 
    return ans
     
     
# Driver Code
if __name__ == "__main__" :
 
    SieveOfEratosthenes()
    n = 21
 
    print(almostPrimes(n))
     
# This code is contributed by ANKITRAI1

C#

// C# program to count almost 
// prime numbers from 1 to n
using System;
 
class GFG
{
 
static int N = 100005;
 
// Create a boolean array "prime[0..n]" 
// and initialize all entries it as 
// true. A value in prime[i] will finally
// be false if i is Not a prime, else true.
static bool []prime = new bool[N];
static void SieveOfEratosthenes()
{
    for(int i = 0; i < N; i++)
    prime[i] = true;
    prime[1] = false;
 
    for (int p = 2; p * p < N; p++)
    {
        // If prime[p] is not changed, 
        // then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (int i = p * 2; i < N; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to count almost
// prime numbers from 1 to n
static int almostPrimes(int n)
{
    // to store required answer
    int ans = 0;
 
    // 6 is first almost prime number
    for (int i = 6; i <= n; i++)
    {
        // to count prime factors
        int c = 0;
        for (int j = 2; j * j <= i; j++) 
        {
            if (i % j == 0)
            {
                // if it is perfect square
                if (j * j == i)
                {
                    if (prime[j])
                        c++;
                }
                else
                {
                    if (prime[j])
                        c++;
                    if (prime[i / j])
                        c++;
                }
            }
        }
 
        // if I is almost prime number
        if (c == 2)
            ans++;
    }
    return ans;
}
 
// Driver code
public static void Main () 
{
    SieveOfEratosthenes();
    int n = 21;
     
    Console.WriteLine( almostPrimes(n));
}
}
 
// This code is contributed 
// by inder_verma

PHP

<?php
// PHP program to count almost prime 
// numbers from 1 to n 
 
$N = 100005;
 
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true. 
// A value in prime[i] will 
// finally be false if i is Not a prime, else true. 
$prime = array_fill(0, $N, true);
 
function SieveOfEratosthenes()
{
    global $N, $prime;
    $prime[1] = false;
 
    for($p = 2; $p < (int)(sqrt($N)); $p++)
    {
        // If prime[p] is not changed, then 
        // it is a prime 
        if ($prime[$p] == true)
         
            // Update all multiples of p 
            for($i = 2 * $p; $i < $N; $i += $p)
                $prime[$i] = false;
    }
}
 
// Function to count almost prime 
// numbers from 1 to n 
function almostPrimes($n)
{
    global $prime;
     
    // to store required answer
    $ans = 0;
 
    // 6 is first almost prime number 
    for($i = 6; $i < $n + 1; $i++)
    {
        // to count prime factors 
        $c = 0;
        for($j = 2; $i >= $j * $j; $j++)
        { 
 
            // if it is perfect square
            if ($i % $j == 0)
            {
                if ($j * $j == $i)
                {
                    if ($prime[$j])
                        $c += 1;
                }
                else
                {
                    if ($prime[$j])
                        $c += 1;
                    if ($prime[($i / $j)]) 
                        $c += 1;
                }
            } 
             
        }
         
    // if I is almost prime number 
    if ($c == 2)
        $ans += 1;
    }
    return $ans;
} 
     
// Driver Code
SieveOfEratosthenes();
$n = 21;
 
print(almostPrimes($n));
 
// This code is contributed by mits
?>

Javascript

<script>
// Javascript program to count almost prime
// numbers from 1 to n
 
let N = 100005;
 
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will
// finally be false if i is Not a prime, else true.
let prime = new Array(N).fill(true);
 
function SieveOfEratosthenes()
{
    prime[1] = false;
 
    for(let p = 2; p < Math.floor(Math.sqrt(N)); p++)
    {
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true)
         
            // Update all multiples of p
            for(let i = 2 * p; i < N; i += p)
                prime[i] = false;
    }
}
 
// Function to count almost prime
// numbers from 1 to n
function almostPrimes(n)
{    
    // to store required answer
    let ans = 0;
 
    // 6 is first almost prime number
    for(let i = 6; i < n + 1; i++)
    {
        // to count prime factors
        let c = 0;
        for(let j = 2; i >= j * j; j++)
        {
 
            // if it is perfect square
            if (i % j == 0)
            {
                if (j * j == i)
                {
                    if (prime[j])
                        c += 1;
                }
                else
                {
                    if (prime[j])
                        c += 1;
                    if (prime[(i / j)])
                        c += 1;
                }
            }
             
        }
         
    // if I is almost prime number
    if (c == 2)
        ans += 1;
    }
    return ans;
}
     
// Driver Code
SieveOfEratosthenes();
let n = 21;
 
document.write(almostPrimes(n));
 
// This code is contributed by _saurabh_jaiswal
</script>

Output:

Time Complexity: O(n^3/2 + 100005^3/2)

Auxiliary Space: O(100005)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!