# Python program to print prime numbers from 1 to n

### Prime number

A prime number is an integer greater than 1 whose only factors are 1 and itself. A factor is an integer that can be divided evenly into another number.

### Logic

To print all the prime numbers up to N, we start one loop from 2 to N and then inside the loop we check current number or “num” is prime or not. To check if it is prime or not we again need one nested loop. It is not an efficient way to check prime number but it is simpler to understand the basic of looping in Python.

### Program

```# Take input from user
upto = int(input("Find prime numbers upto : "))

print("\nAll prime numbers upto", upto, "are : ")

for num in range(2, upto + 1):

i = 2

for i in range(2, num):
if(num % i == 0):
i = num
break;

# If the number is prime then print it.
if(i != num):
print(num, end=" ")```

#### Output

```Find prime numbers upto : 100 All prime numbers upto 100 are : 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97```

View Discussion

Improve Article

Save Article

• Discuss
• View Discussion

Improve Article

Save Article

Given a number N, the task is to print the prime numbers from 1 to N.
Examples:

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

Input: N = 5
Output: 2, 3, 5 ```

Algorithm:

• First, take the number N as input.
• Then use a for loop to iterate the numbers from 1 to N
• Then check for each number to be a prime number. If it is a prime number, print it.

Approach 1:  Now, according to formal definition, a number ‘n’ is prime if it is not divisible by any number other than 1 and n. In other words a number is prime if it is not divisible by any number from 2 to n-1.

Below is the implementation of the above approach:

## C++

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`bool` `isPrime(``int` `n)`

`{`

`    ``if` `(n == 1 || n == 0)`

`        ``return` `false``;`

`    ``for` `(``int` `i = 2; i < n; i++) {`

`        ``if` `(n % i == 0)`

`            ``return` `false``;`

`    ``}`

`    ``return` `true``;`

`}`

`int` `main()`

`{`

`    ``int` `N = 100;`

`    ``for` `(``int` `i = 1; i <= N; i++) {`

`        ``if` `(isPrime(i))`

`            ``cout << i << ``" "``;`

`    ``}`

`    ``return` `0;`

`}`

## C

`#include <stdbool.h>`

`#include <stdio.h>`

`bool` `isPrime(``int` `n)`

`{`

`    ``if` `(n == 1 || n == 0)`

`        ``return` `false``;`

`    ``for` `(``int` `i = 2; i < n; i++) {`

`        ``if` `(n % i == 0)`

`            ``return` `false``;`

`    ``}`

`    ``return` `true``;`

`}`

`int` `main()`

`{`

`    ``int` `N = 100;`

`    ``for` `(``int` `i = 1; i <= N; i++) {`

`        ``if` `(isPrime(i))`

`            ``printf``(``"%d "``, i);`

`    ``}`

`    ``return` `0;`

`}`

## Java

`class` `GFG `

`{`

`     ``static` `boolean` `isPrime(``int` `n){`

`          ``if``(n==``1``||n==``0``)``return` `false``;`

`          ``for``(``int` `i=``2``; i<n; i++){`

`                ``if``(n%i==``0``)``return` `false``;`

`          ``}`

`          ``return` `true``;`

`    ``}`

`    ``public` `static` `void` `main (String[] args) `

`    ``{ `

`        ``int` `N = ``100``; `

`        ``for``(``int` `i=``1``; i<=N; i++){`

`            ``if``(isPrime(i)) {`

`                ``System.out.print(i + ``" "``);`

`            ``}`

`        ``}`

`    ``}`

`}`

## Python3

`def` `isPrime(n):`

`  ``if``(n``=``=``1` `or` `n``=``=``0``):`

`    ``return` `False`

`  ``for` `i ``in` `range``(``2``,n):`

`    ``if``(n``%``i``=``=``0``):`

`      ``return` `False`

`  ``return` `True`

`N ``=` `100``;`

`for` `i ``in` `range``(``1``,N``+``1``):`

`  ``if``(isPrime(i)):`

`    ``print``(i,end``=``" "``)`

## C#

`using` `System;`

`class` `GFG `

`{`

`     ``static` `bool` `isPrime(``int` `n){`

`        ``if``(n==1||n==0) ``return` `false``;`

`        ``for``(``int` `i=2; i<n; i++) {`

`            ``if``(n%i==0) ``return` `false``;`

`        ``}`

`      ``return` `true``;`

`    ``}`

`    ``public` `static` `void` `Main (String[] args) `

`    ``{ `

`        ``int` `N = 100; `

`        ``for``(``int` `i=1; i<=N; i++) {`

`            ``if``(isPrime(i)) {`

`              ``Console.Write(i + ``" "``); `

`            ``}`

`        ``}`

`    ``}`

`}`

## Javascript

`<script>`

`function` `isPrime( n)`

`{`

`      ``if``(n == 1 || n == 0) ``return` `false``;`

`      ``for``(``var` `i = 2; i < n; i++)`

`      ``{`

`        ``if``(n % i == 0) ``return` `false``;`

`      ``}`

`      ``return` `true``;`

`}`

`var` `N = 100;`

`  ``for``(``var` `i = 1; i <= N; i++)`

`  ``{`

`      ``if``(isPrime(i)) {`

`        ``console.log( i );`

`      ``}`

`}`

`</script>`

Output

`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 `

Time Complexity: O(N^2),

Auxiliary Space: O(1)

Approach 2:  For checking if a number is prime or not do we really need to iterate through all the number from 2 to n-1? We already know that a number ‘n’ cannot be divided by any number greater than ‘n/2’. So, according to this logic we only need to iterate through 2 to n/2 since number greater than n/2 cannot divide n.

## C++

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`bool` `isPrime(``int` `n){`

`    ``if``(n==1||n==0) ``return` `false``;`

`    ``for``(``int` `i=2; i<=n/2; i++) {`

`          ``if``(n%i==0) ``return` `false``;`

`    ``}`

`    ``return` `true``;`

`}`

`int` `main()`

`{`

`    ``int` `N = 100;`

`      ``for``(``int` `i=1; i<=N; i++){`

`        ``if``(isPrime(i)) {`

`          ``cout << i << ``" "``;`

`        ``}`

`    ``}`

`    ``return` `0;`

`}`

## Java

`class` `GFG `

`{`

`     ``static` `boolean` `isPrime(``int` `n){`

`          ``if``(n==``1``||n==``0``) ``return` `false``;`

`        ``for``(``int` `i=``2``; i<=n/``2``; i++){`

`            ``if``(n%i==``0``)``return` `false``;`

`        ``}`

`        ``return` `true``;`

`    ``}`

`    ``public` `static` `void` `main (String[] args) `

`    ``{ `

`        ``int` `N = ``100``; `

`        ``for``(``int` `i=``1``; i<=N; i++){`

`            ``if``(isPrime(i)) {`

`              ``System.out.print(i + ``" "``);`

`            ``}`

`        ``}`

`    ``}`

`}`

## Python3

`def` `isPrime(n):`

`  ``if``(n``=``=``1` `or` `n``=``=``0``):`

`    ``return` `False`

`  ``for` `i ``in` `range``(``2``,(n``/``/``2``)``+``1``):`

`    ``if``(n``%``i``=``=``0``):`

`      ``return` `False`

`  ``return` `True`

`N ``=` `100``;`

`for` `i ``in` `range``(``1``,N``+``1``):`

`  ``if``(isPrime(i)):`

`    ``print``(i,end``=``" "``)`

## C#

`using` `System;`

`class` `GFG `

`{`

` ``static` `bool` `isPrime(``int` `n){`

`     ``if``(n==1||n==0)``return` `false``;`

`      ``for``(``int` `i=2; i<=n/2; i++){`

`        ``if``(n%i==0)``return` `false``;`

`      ``}`

`  ``return` `true``;`

`}`

`public` `static` `void` `Main (String[] args) `

`{ `

`    ``int` `N = 100; `

`      ``for``(``int` `i=1; i<=N; i++){`

`      ``if``(isPrime(i)) {`

`        ``Console.Write(i + ``" "``); `

`      ``}`

`    ``}`

`}`

`}`

## Javascript

`<script>`

`function` `isPrime(n)`

`{`

`    ``if``(n == 1 || n == 0) ``return` `false``;`

`    ``for``(let i = 2; i <= n / 2; i++)`

`    ``{`

`          ``if``(n % i == 0) ``return` `false``;`

`    ``}`

`    ``return` `true``;`

`}`

`let N = 100;`

`for``(let i = 1; i <= N; i++)`

`{`

`    ``if``(isPrime(i)) `

`    ``{`

`        ``document.write(i + ``" "``);`

`    ``}`

`}`

`</script>`

Output

`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 `

Time Complexity: O(N2),

Auxiliary Space: O(1),since no extra space has been taken.

Approach 3: If a number ‘n’ is not divided by any number less than or equals to the square root of n then, it will not be divided by any other number greater than the square root of n. So, we only need to check up to the square root of n.

## C++

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`bool` `isPrime(``int` `n){`

`  ``if``(n==1||n==0)``return` `false``;`

`  ``for``(``int` `i=2; i*i<=n; i++){`

`    ``if``(n%i==0)``return` `false``;`

`  ``}`

`  ``return` `true``;`

`}`

`int` `main()`

`{`

`    ``int` `N = 100;`

`      ``for``(``int` `i=1; i<=N; i++){`

`      ``if``(isPrime(i)) {`

`        ``cout << i << ``" "``;`

`      ``}`

`    ``}`

`    ``return` `0;`

`}`

## Java

`class` `GFG `

`{`

` ``static` `boolean` `isPrime(``int` `n){`

`  ``if``(n==``1``||n==``0``)``return` `false``;`

`  ``for``(``int` `i=``2``; i*i<=n; i++){`

`    ``if``(n%i==``0``)``return` `false``;`

`  ``}`

`  ``return` `true``;`

`}`

`public` `static` `void` `main (String[] args) `

`{ `

`    ``int` `N = ``100``; `

`      ``for``(``int` `i=``1``; i<=N; i++){`

`      ``if``(isPrime(i)) {`

`        ``System.out.print(i + ``" "``);`

`      ``}`

`    ``}`

`}`

`}`

## Python3

`def` `isPrime(n):`

`  ``if``(n``=``=``1` `or` `n``=``=``0``):`

`    ``return` `False`

`  ``for` `i ``in` `range``(``2``,``int``(n``*``*``(``1``/``2``))``+``1``):`

`    ``if``(n``%``i``=``=``0``):`

`      ``return` `False`

`  ``return` `True`

`N ``=` `100``;`

`for` `i ``in` `range``(``1``,N``+``1``):`

`  ``if``(isPrime(i)):`

`    ``print``(i,end``=``" "``)`

## C#

`using` `System;`

`class` `GFG `

`{`

` ``static` `bool` `isPrime(``int` `n){`

`     ``if``(n==1||n==0)``return` `false``;`

`      ``for``(``int` `i=2; i*i<=n; i++){`

`        ``if``(n%i==0)``return` `false``;`

`      ``}`

`  ``return` `true``;`

`}`

`public` `static` `void` `Main (String[] args) `

`{ `

`    ``int` `N = 100; `

`      ``for``(``int` `i=1; i<=N; i++){`

`      ``if``(isPrime(i)) {`

`        ``Console.Write(i + ``" "``); `

`      ``}`

`    ``}`

`}`

`}`

## Javascript

`<script>`

`const isPrime = (n) => {`

`    ``if``(n === 1||n === 0)``return` `false``;`

`    ``for``(let i = 2; i <= Math.floor(Math.sqrt(n)); i++)`

`    ``{`

`      ``if``(n % i == 0)``return` `false``;`

`    ``}`

`    ``return` `true``;`

`  ``}`

`  ``let N = 100;`

`  ``for``(let i=1; i<=N; i++)`

`  ``{`

`      ``if``(isPrime(i)) {`

`          ``document.write(i);`

`      ``}`

`  ``}`

`  ``</script>`

Output

`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 `

Time Complexity: O(N^(3/2)),

Auxiliary Space: O(1)

You can further optimize the time complexity to O(n*log(log(n))). CheckSieve of Eratosthenes.

### How do you find a prime number from 1 to n?

C program for prime numbers between 1 to n.
#include<stdio.h>.
int main(){.
int num,i,count,n; printf("Enter max range: ");.
scanf("%d",&n);.
for(num = 1;num<=n;num++){.
count = 0;.
for(i=2;i<=num/2;i++){ if(num%i==0){.
count++; break;.

### How do you find the prime numbers from 1 to 50 in python?

lower = int(input("Enter lower range: ")).
upper = int(input("Enter upper range: ")).
for num in range(lower,upper + 1):.
if num > 1:.
for i in range(2,num):.
if (num % i) == 0:.
break..

### How do you find prime numbers from 1 to 1000 in Python?

for num in range(1,1001): if num > 1: for i in range(2,num): if (num % i) == 0: break else: print(num,"is a prime number!") First thing would be, if num >= 1: after that, you have if (num % i) == 0 break that is why it is stopping there.

### How do you find all prime numbers up to n?

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.

Tải thêm tài liệu liên quan đến bài viết Python program to print prime numbers from 1 to n