Given a number N. Find number of almost primes from 1 to 
. 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 nint 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 codeint 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 nint 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 codeint 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 nimport 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 nstatic 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 everythingfrom 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] * Ndef 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 Codeif __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 nusing 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 nstatic 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 codepublic 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 CodeSieveOfEratosthenes();$n = 21;print(almostPrimes($n));// This code is contributed by mits?> |
Javascript
<script>// Javascript program to count almost prime// numbers from 1 to nlet 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 nfunction 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 CodeSieveOfEratosthenes();let n = 21;document.write(almostPrimes(n));// This code is contributed by _saurabh_jaiswal</script> |
Output:
8
Time Complexity: O(n3/2 + 1000053/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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you can find 79604 additional Information to that Topic: geeksforgeeks.org/find-count-of-almost-prime-numbers-from-1-to-n/ […]