Блог

Главная - Python язык программирования - Программа для печати простых чисел от 1 до N
You are currently viewing Программа для печати простых чисел от 1 до N

Программа для печати простых чисел от 1 до N

Учитывая число N, задача состоит в том, чтобы вывести простые числа от 1 до N.

Примеры:

Input: N = 10
Output: 2, 3, 5, 7

Input: N = 5
Output: 2, 3, 5
  • Во-первых, возьмите число N в качестве входных данных.
  • Затем используйте цикл for для повторения чисел от 1 до N
  • Затем проверьте, чтобы каждое число было простым числом. Если это простое число, выведите его.

Подход 1: Теперь, согласно формальному определению, число » n » является простым, если оно не делится ни на одно число, кроме 1 и n. Другими словами, число является простым, если оно не делится ни на какое число от 2 до n-1.

Ниже приводится реализация вышеупомянутого подхода:

// C++ program to display first N Prime numbers
#include <bits/stdc++.h>
using namespace std;

//function to check if a given number is prime
bool isPrime(int n){
	//since 0 and 1 is not prime return false.
	if(n==1||n==0) return false;

	//Run a loop from 2 to n-1
	for(int i=2; i<n; i++){
		// if the number is divisible by i, then n is not a prime number.
		if(n%i==0) return false;
	}
	//otherwise, n is prime number.
	return true;
}


// Driver code
int main()
{
	int N = 100;

	//check for every number from 1 to N
	for(int i=1; i<=N; i++){
		//check if current number is prime
		if(isPrime(i)) {
			cout << i << " ";
		}
	}

	return 0;
}

// Java program to display
// first N Prime numbers
class GFG
{
	//function to check if a given number is prime
	static boolean isPrime(int n){
		//since 0 and 1 is not prime return false.
		if(n==1||n==0)return false;

		//Run a loop from 2 to n-1
		for(int i=2; i<n; i++){
			// if the number is divisible by i, then n is not a prime number.
				if(n%i==0)return false;
		}
		//otherwise, n is prime number.
		return true;
	}
	

	// Driver code
	public static void main (String[] args)
	{
		int N = 100;
		//check for every number from 1 to N
		for(int i=1; i<=N; i++){
			//check if current number is prime
			if(isPrime(i)) {
				System.out.print(i + " ");
			}
		}

	}
}

# Python3 program to display first N Prime numbers

#function to check if a given number is prime
def isPrime(n):
#since 0 and 1 is not prime return false.
if(n==1 or n==0):
	return False

#Run a loop from 2 to n-1
for i in range(2,n):
	#if the number is divisible by i, then n is not a prime number.
	if(n%i==0):
	return False

#otherwise, n is prime number.
return True



# Driver code
N = 100;
#check for every number from 1 to N
for i in range(1,N+1):
#check if current number is prime
if(isPrime(i)):
	print(i,end=" ")

// C# program to display
// first N Prime numbers
using System;
	
class GFG
{

	//function to check if a given number is prime
	static bool isPrime(int n){
		//since 0 and 1 is not prime return false.
		if(n==1||n==0) return false;

		//Run a loop from 2 to n-1
		for(int i=2; i<n; i++) {
			// if the number is divisible by i, then n is not a prime number.
			if(n%i==0) return false;
		}
	//otherwise, n is prime number.
	return true;
	}

	// Driver code
	public static void Main (String[] args)
	{
		int N = 100;
		//check for every number from 1 to N
		for(int i=1; i<=N; i++) {
		//check if current number is prime
			if(isPrime(i)) {
			Console.Write(i + " ");
			}
		}

	}
}

// This code is contributed by Rajput-Ji

<script>

// JavaScript program to display first N Prime numbers

// function to check if a given number is prime
function isPrime( n)
{
	// since 0 and 1 is not prime return false.
	if(n == 1 || n == 0) return false;

	// Run a loop from 2 to n-1
	for(var i = 2; i < n; i++)
	{
	
		// if the number is divisible by i, then n is not a prime number.
		if(n % i == 0) return false;
	}
	// otherwise, n is prime number.
	return true;
}


// Driver code
var N = 100;

// check for every number from 1 to N
for(var i = 1; i <= N; i++)
{
	// check if current number is prime
	if(isPrime(i)) {
		console.log( i );
	}
}

// This code is contributed by ukasp.
</script>

Выход:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Временная сложность: O(N^2), Пространственная Сложность: O(1)

Подход 2: Для проверки, является ли число простым или нет, действительно ли нам нужно выполнить итерацию по всей форме чисел от 2 до n-1? Мы уже знаем, что число » n «не может быть разделено ни на какое число, большее, чем «n/2». Итак, в соответствии с этой логикой нам нужно только выполнить итерацию от 2 до n/2, так как число, большее n/2, не может разделить n.

// C++ program to display first N Prime numbers
#include <bits/stdc++.h>
using namespace std;

//function to check if a given number is prime
bool isPrime(int n){
	//since 0 and 1 is not prime return false.
	if(n==1||n==0) return false;

	//Run a loop from 2 to n/2.
	for(int i=2; i<=n/2; i++) {
		// if the number is divisible by i, then n is not a prime number.
		if(n%i==0) return false;
	}
	//otherwise, n is prime number.
	return true;
}


// Driver code
int main()
{
	int N = 100;

	//check for every number from 1 to N
	for(int i=1; i<=N; i++){
		//check if current number is prime
		if(isPrime(i)) {
		cout << i << " ";
		}
	}

	return 0;
}

// Java program to display
// first N Prime numbers
class GFG
{
	//function to check if a given number is prime
	static boolean isPrime(int n){
		//since 0 and 1 is not prime return false.
		if(n==1||n==0) return false;

		//Run a loop from 2 to n-1
		for(int i=2; i<=n/2; i++){
			// if the number is divisible by i, then n is not a prime number.
			if(n%i==0)return false;
		}
		//otherwise, n is prime number.
		return true;
	}
	

	// Driver code
	public static void main (String[] args)
	{
		int N = 100;
		//check for every number from 1 to N
		for(int i=1; i<=N; i++){
			//check if current number is prime
			if(isPrime(i)) {
			System.out.print(i + " ");
			}
		}

	}
}

# Python3 program to display first N Prime numbers

#function to check if a given number is prime
def isPrime(n):
#since 0 and 1 is not prime return false.
if(n==1 or n==0):
	return False

#Run a loop from 2 to n/2
for i in range(2,(n//2)+1):
	#if the number is divisible by i, then n is not a prime number.
	if(n%i==0):
	return False

#otherwise, n is prime number.
return True



# Driver code
N = 100;
#check for every number from 1 to N
for i in range(1,N+1):
#check if current number is prime
if(isPrime(i)):
	print(i,end=" ")

// C# program to display
// first N Prime numbers
using System;
	
class GFG
{

//function to check if a given number is prime
static bool isPrime(int n){
	//since 0 and 1 is not prime return false.
	if(n==1||n==0)return false;

	//Run a loop from 2 to n/2.
	for(int i=2; i<=n/2; i++){
		// if the number is divisible by i, then n is not a prime number.
		if(n%i==0)return false;
	}
//otherwise, n is prime number.
return true;
}

// Driver code
public static void Main (String[] args)
{
	int N = 100;
	//check for every number from 1 to N
	for(int i=1; i<=N; i++){
	//check if current number is prime
	if(isPrime(i)) {
		Console.Write(i + " ");
	}
	}
	
}
}

// This code is contributed by Rajput-Ji

Выход:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Временная сложность: O(N^2), Пространственная Сложность: O(1)

Подход 3: Если число » n » не делится ни на какое число, меньшее или равное квадратному корню из n, то оно не будет разделено ни на какое другое число, большее квадратного корня из n. Итак, нам нужно только проверить квадратный корень из n.

// C++ program to display first N Prime numbers
#include <bits/stdc++.h>
using namespace std;

//function to check if a given number is prime
bool isPrime(int n){
//since 0 and 1 is not prime return false.
if(n==1||n==0)return false;

//Run a loop from 2 to square root of n.
for(int i=2; i*i<=n; i++){
	// if the number is divisible by i, then n is not a prime number.
	if(n%i==0)return false;
}
//otherwise, n is prime number.
return true;
}


// Driver code
int main()
{
	int N = 100;

	//check for every number from 1 to N
	for(int i=1; i<=N; i++){
	//check if current number is prime
	if(isPrime(i)) {
		cout << i << " ";
	}
	}

	return 0;
}

// Java program to display
// first N Prime numbers
class GFG
{
//function to check if a given number is prime
static boolean isPrime(int n){
//since 0 and 1 is not prime return false.
if(n==1||n==0)return false;

//Run a loop from 2 to square root of n
for(int i=2; i*i<=n; i++){
	// if the number is divisible by i, then n is not a prime number.
	if(n%i==0)return false;
}
//otherwise, n is prime number.
return true;
}
	

// Driver code
public static void main (String[] args)
{
	int N = 100;
		//check for every number from 1 to N
	for(int i=1; i<=N; i++){
	//check if current number is prime
	if(isPrime(i)) {
		System.out.print(i + " ");
	}
	}
	
}
}

# Python3 program to display first N Prime numbers

#function to check if a given number is prime
def isPrime(n):
#since 0 and 1 is not prime return false.
if(n==1 or n==0):
	return False

#Run a loop from 2 to square root of n.
for i in range(2,int(n**(1/2))+1):
	#if the number is divisible by i, then n is not a prime number.
	if(n%i==0):
	return False

#otherwise, n is prime number.
return True



# Driver code
N = 100;
#check for every number from 1 to N
for i in range(1,N+1):
#check if current number is prime
if(isPrime(i)):
	print(i,end=" ")

// C# program to display
// first N Prime numbers
using System;
	
class GFG
{

//function to check if a given number is prime
static bool isPrime(int n){
	//since 0 and 1 is not prime return false.
	if(n==1||n==0)return false;

	//Run a loop from 2 to square root of n.
	for(int i=2; i*i<=n; i++){
		// if the number is divisible by i, then n is not a prime number.
		if(n%i==0)return false;
	}
//otherwise, n is prime number.
return true;
}

// Driver code
public static void Main (String[] args)
{
	int N = 100;
	//check for every number from 1 to N
	for(int i=1; i<=N; i++){
	//check if current number is prime
	if(isPrime(i)) {
		Console.Write(i + " ");
	}
	}
	
}
}

// This code is contributed by Rajput-Ji

Выход:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Временная сложность: O(N^(3/2)), Пространственная Сложность: O(1)

Вы можете дополнительно оптимизировать временную сложность, чтобы O(n*журнал(журнал(n))).

Метки: