Dado un número N, la tarea es imprimir todos los números primos menores o iguales que N.
Ejemplos:
Input: 7 Output: 2, 3, 5, 7 Input: 13 Output: 2, 3, 5, 7, 11, 13
Enfoque ingenuo: iterar de 2 a N y comprobar si hay primos . Si es un número primo, imprima el número.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all primes
// less than N
#include <bits/stdc++.h>
using namespace std;
// function check whether a number
// is prime or not
bool isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to print primes
void printPrime(int n)
{
for (int i = 2; i <= n; i++) {
if (isPrime(i))
cout << i << " ";
}
}
// Driver Code
int main()
{
int n = 7;
printPrime(n);
}
Python3
# Python3 program to print # all primes less than N # Function to check whether # a number is prime or not . def isPrime(n): # Corner case if n <= 1 : return False # check from 2 to n-1 for i in range(2, n): if n % i == 0: return False return True # Function to print primes def printPrime(n): for i in range(2, n + 1): if isPrime(i): print(i, end = " ") # Driver code if __name__ == "__main__" : n = 7 # function calling printPrime(n) # This code is contributed # by Ankit Rai
Java
// Java program to print
// all primes less than N
class GFG
{
// function check whether
// a number is prime or not
static boolean isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to print primes
static void printPrime(int n)
{
for (int i = 2; i <= n; i++)
{
if (isPrime(i))
System.out.print(i + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int n = 7;
printPrime(n);
}
}
// This code is contributed
// by ChitraNayal
C#
// C# program to print
// all primes less than N
using System;
class GFG
{
// function check whether
// a number is prime or not
static bool isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to print primes
static void printPrime(int n)
{
for (int i = 2; i <= n; i++)
{
if (isPrime(i))
Console.Write(i + " ");
}
}
// Driver Code
public static void Main()
{
int n = 7;
printPrime(n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to print
// all primes less than N
// function check whether
// a number is prime or not
function isPrime($n)
{
// Corner case
if ($n <= 1)
return false;
// Check from 2 to n-1
for ($i = 2; $i < $n; $i++)
if ($n % $i == 0)
return false;
return true;
}
// Function to print primes
function printPrime($n)
{
for ($i = 2; $i <= $n; $i++)
{
if (isPrime($i))
echo $i . " ";
}
}
// Driver Code
$n = 7;
printPrime($n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to print all primes
// less than N
// function check whether a number
// is prime or not
function isPrime(n)
{
// Corner case
if (n <= 1)
return false;
// Check from 2 to n-1
for (let i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to print primes
function printPrime(n)
{
for (let i = 2; i <= n; i++) {
if (isPrime(i))
document.write(i +" ");
}
}
// Driver Code
let n = 7;
printPrime(n);
// This code is contributed by Mayank Tyagi
</script>
Producción:
2 3 5 7
Complejidad temporal: O(N * N)
Un mejor enfoque se basa en el hecho de que uno de los divisores debe ser menor o igual que √n. Entonces verificamos la divisibilidad solo hasta √n.
C++
// C++ program to print all primes
// less than N
#include <bits/stdc++.h>
using namespace std;
// function check whether a number
// is prime or not
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to print primes
void printPrime(int n)
{
for (int i = 2; i <= n; i++) {
if (isPrime(i))
cout << i << " ";
}
}
// Driver Code
int main()
{
int n = 7;
printPrime(n);
}
Java
// Java program to print
// all primes less than N
import java.io.*;
class GFG
{
// function check
// whether a number
// is prime or not
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so
// that we can skip
// middle five numbers
// in below loop
if (n % 2 == 0 ||
n % 3 == 0)
return false;
for (int i = 5;
i * i <= n; i = i + 6)
if (n % i == 0 ||
n % (i + 2) == 0)
return false;
return true;
}
// Function to print primes
static void printPrime(int n)
{
for (int i = 2; i <= n; i++)
{
if (isPrime(i))
System.out.print(i + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int n = 7;
printPrime(n);
}
}
// This code is contributed
// by anuj_67.
C#
// C# program to print
// all primes less than N
using System;
class GFG
{
// function check
// whether a number
// is prime or not
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so
// that we can skip
// middle five numbers
// in below loop
if (n % 2 == 0 ||
n % 3 == 0)
return false;
for (int i = 5;
i * i <= n; i = i + 6)
if (n % i == 0 ||
n % (i + 2) == 0)
return false;
return true;
}
// Function to print primes
static void printPrime(int n)
{
for (int i = 2; i <= n; i++)
{
if (isPrime(i))
Console.Write(i + " ");
}
}
// Driver Code
public static void Main ()
{
int n = 7;
printPrime(n);
}
}
// This code is contributed
// by ChitraNayal
Python3
# function to check if the number is # prime or not def isPrime(n) : # Corner cases if (n <= 1) : return False if (n <= 3) : return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0) : return False i = 5 while(i * i <= n) : if (n % i == 0 or n % (i + 2) == 0) : return False i = i + 6 return True # print all prime numbers # less than equal to N def printPrime(n): for i in range(2, n + 1): if isPrime(i): print (i, end =" ") n = 7 printPrime(n)
Javascript
<script>
// Javascript program to print all primes
// less than N
// function check whether a number
// is prime or not
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to print primes
function printPrime(n)
{
for (let i = 2; i <= n; i++) {
if (isPrime(i))
document.write(i + " ");
}
}
// Driver Code
let n = 7;
printPrime(n);
// This code is contributed by subhammahato348.
</script>
PHP
<?php
// PHP program to print
// all primes less than N
// function check whether
// a number is prime or not
function isPrime($n)
{
// Corner cases
if ($n <= 1)
return false;
if ($n <= 3)
return true;
// This is checked so that
// we can skip middle five
// numbers in below loop
if ($n % 2 == 0 || $n % 3 == 0)
return false;
for ($i = 5;
$i * $i <= $n; $i = $i + 6)
if ($n % $i == 0 ||
$n % ($i + 2) == 0)
return false;
return true;
}
// Function to print primes
function printPrime($n)
{
for ($i = 2; $i <= $n; $i++)
{
if (isPrime($i))
echo $i . " ";
}
}
// Driver Code
$n = 7;
printPrime($n);
// This code is contributed
// by ChitraNayal
?>
Producción:
2 3 5 7
Complejidad temporal: O(N 3/2 )
La mejor solución es utilizar Tamiz de Eratóstenes . La complejidad del tiempo es O(N * loglog(N))
Publicación traducida automáticamente
Artículo escrito por MuskanChoudhary y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA