Encuentra el conteo de números casi primos del 1 al N

Dado un número N. Encuentra el número de casi primos de 1 a  norte    . Un número se llama casi si tiene exactamente dos factores primos distintos. 
Nota : los números pueden tener cualquier número de factores no primos, pero deben tener exactamente dos factores primos.
Ejemplos
 

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

Input : N = 21
Output : 8

Una solución eficiente es encontrar números primos usando la Criba de Eratóstenes . Y encuentre distintos factores primos que cuenten para números menores que N.
Consulte : Números casi primos
A continuación se muestra la implementación del enfoque anterior: 
 

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>
Producción: 

8

 

Publicación traducida automáticamente

Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *