**Prime numbers** are the natural numbers that are greater than 1 and can only be evenly divided by 1 and themselves.

In this blog post, we will discuss prime numbers, their history, properties, how to print them in different programming languages such as C#, C, C++, JAVA, PHP, and Python, and a comparison of prime vs. composite numbers.

Table of Contents

- 1 What are the prime numbers?
- 2 History of Prime Numbers
- 3 Properties of Prime Numbers
- 4 List of Prime Numbers 1 to 200
- 5 How to Print Prime Numbers from 1 to 100 in Java?
- 6 How to Print Prime Numbers in C?
- 7 How to Print Prime Numbers in C++?
- 8 How to Print Prime Numbers in Python?
- 9 Prime Numbers vs Composite Numbers
- 10 Sieve of Eratosthenes
- 11 Example:
- 12 Goldbach’s Conjecture
- 13 Prime Factorization
- 14 Mersenne Primes
- 15 Twin Primes
- 16 FAQs
- 16.1 Q: What are prime numbers?
- 16.2 Q: Why are prime numbers important?
- 16.3 Q: How can I generate a list of prime numbers?
- 16.4 Q: What is the difference between prime and composite numbers?
- 16.5 Q: How can I check if a number is prime or composite?
- 16.6 Q: What is the time complexity of the Sieve of Eratosthenes algorithm?
- 16.7 Q: Can the Sieve of Eratosthenes algorithm be parallelized?
- 16.8 Related

## What are the prime numbers?

**Prime numbers are the natural numbers that are greater than 1 and are divisible only by 1 and themselves**. In other words, a prime number has only two factors – 1 and the number itself.

For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97 are the prime numbers up to 100. The list of prime numbers goes on infinitely.

## History of Prime Numbers

The concept of prime numbers has been studied for thousands of years. It is believed that the ancient Greeks were the first to recognize prime numbers as a distinct mathematical concept. Pythagoras and his followers were particularly interested in the properties of prime numbers.

The Sieve of Eratosthenes, a method for finding prime numbers, was developed by the Greek mathematicianÂ EratosthenesÂ around 240 BCE. This method systematically eliminates multiples of each prime number until only the primes remain.

Many mathematicians significantly contributed to studying prime numbers in the centuries that followed. One of the most notable was the French mathematician Pierre de Fermat who, in the 17th century, famously wrote in the margin of a book that he had discovered a proof for what is now known as Fermat’s Little Theorem. However, he did not provide the actual proof.

Another important figure in the history of prime numbers was the German mathematician “Carl Friedrich Gauss” in the early 19th century, proved the fundamental theorem of arithmetic, which states that every integer greater than 1 can be uniquely represented as a product of primes.

Today, prime numbers continue to be an important area of research in mathematics, with applications in fields such as cryptography and computer science.

The code example in C#:

```
using System;
class PrimeNumbersInCSharp
{
public static void Main()
{
int n, i, m = 0, flag = 0;
Console.Write("Enter the number to check prime: ");
n = int.Parse(Console.ReadLine());
m = n / 2;
for (i = 2; i <= m; i++)
{
if (n % i == 0)
{
Console.WriteLine($"Number {n} is not Prime.");
flag = 1;
break;
}
}
if (flag == 0)
Console.WriteLine($"Number {n} is Prime.");
}
}
```

**Output:**

```
Enter the number to check prime: 5
Number 5 is Prime.
```

## Properties of Prime Numbers

Here are some properties of prime numbers:

- A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.
- Every composite number can be expressed as a product of prime numbers.
- The number 1 is not a prime number because it has only one factor.
- The sum of two prime numbers is only sometimes a prime number. For example, 3 + 5 = 8, which is not a prime number.
- The difference between two prime numbers is not always a prime number. For example, 5 – 3 = 2, which is a prime number, but 7 – 5 = 2, which is also a prime number.
- The product of two prime numbers is always a composite number.
- Every prime number greater than 3 can be expressed as 6n Â± 1, where n is a natural number.
- Every even prime number is 2.
- The sum of the reciprocals of the prime numbers diverges.

## List of Prime Numbers 1 to 200

The following is the list of prime numbers from 1 to 200:

Range of numbers Prime numbers

Range of numbers | Prime numbers |
---|---|

Prime numbers between 1 and 20 | 2, 3, 5, 7, 11, 13, 17, 19 |

Prime numbers between 20 and 40 | 23, 29, 31, 37 |

Prime numbers between 40 and 60 | 41, 43, 47, 53, 59 |

Prime numbers between 60 and 80 | 61, 67, 71, 73, 79 |

Prime numbers between 80 and 100 | 83, 89, 97 |

Prime numbers between 100 and 120 | 01, 103, 107, 109, 113 |

Prime numbers between 120 and 140 | 127, 131, 137 |

Prime numbers between 140 and 160 | 139, 149, 151, 157 |

Prime numbers between 160 and 180 | 163, 167, 173, 179 |

Prime numbers between 180 and 200 | 181, 191, 193, 197, 199 |

## How to Print Prime Numbers from 1 to 100 in Java?

Java is one of the most popular programming languages in the world. Here is an example Java program to print prime numbers from 1 to 100.

```
public class PrimeNumbers {
public static void main(String[] args) {
int i, j, flag;
for (i = 1; i <= 100; i++) {
if (i == 1 || i == 0)
continue;
flag = 1;
for (j = 2; j <= i / 2; ++j) {
if (i % j == 0) {
flag = 0;
break;
}
}
if (flag == 1)
System.out.println(i);
}
}
}
```

The above Java program uses a nested for loop to check whether a number is a prime. The outer loop runs from 1 to 100, while the inner loop checks if the number is divisible by any number other than 1 and itself. If the number is not divisible by any number other than 1 and itself, it is a prime number and is printed.

## How to Print Prime Numbers in C?

C is a powerful programming language widely used in systems programming, embedded systems, and game development. Here is an example of a C program to print all prime numbers between 1 to n numbers.

```
#include <stdio.h>
int main()
{
int n, i, j, flag;
printf("Enter a number n: ");
scanf("%d", &n);
printf("Prime numbers between 1 and %d are: ", n);
for (i = 2; i <= n; i++) {
flag = 1;
for (j = 2; j <= i / 2; ++j) {
if (i % j == 0) {
flag = 0;
break;
}
}
if (flag == 1)
printf("%d ", i);
}
return 0;
}
```

The above C program prompts the user to enter a number and then uses a nested for loop to check whether a number is a prime. If the number is prime, it is printed.

**Output:**

```
Enter a number n: 100
Prime numbers between 1 and 100 are: 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
```

## How to Print Prime Numbers in C++?

Printing prime numbers in C++ is similar to the process in other programming languages. Here is a simple program that prints all the prime numbers between 1 and a user-defined limit:

```
#include <iostream>
using namespace std;
int main() {
int limit, i, j;
bool isPrime;
// Get user input for limit
cout << "Enter limit: ";
cin >> limit;
// Print prime numbers
cout << "Prime numbers between 1 and " << limit << " are: ";
for(i=2; i<=limit; i++) {
isPrime = true;
for(j=2; j<i; j++) {
if(i%j == 0) {
isPrime = false;
break;
}
}
if(isPrime) {
cout << i << " ";
}
}
return 0;
}
```

In this program, we first get user input to print the limit of prime numbers. We then loop through all the numbers from 2 to the limit and check whether each number is prime.

To check if a number is a prime, we use a nested for loop that loops through all the numbers from 2 to i-1.Â

If i is divisible by any of these numbers, then it is not a prime number, and we set theÂ `isPrime`

Â flag to false. Otherwise, it is a prime number, and we print it out.

**Output:**

```
Enter limit: 10
Prime numbers between 1 and 10 are: 2 3 5 7
```

## How to Print Prime Numbers in Python?

In Python, there are multiple ways to print prime numbers.

Here is an example of using a for loop to print all prime numbers from 1 to 100:

```
for num in range(1,101):
if all(num%i!=0 for i in range(2,num)):
print(num)
```

In this code, we are using a loop to iterate through the numbers from 1 to 100. For each number, we check if it is a prime number or not using the all function and a generator expression that generates numbers from 2 to num-1.

If any of these numbers divide the current number without a remainder, then it is not a prime number, and the all function returns False.

If the all function returns True, then we know that the current number is a prime number, and we print it.

*You can modify the upper limit of the loop to print prime numbers up to any limit you want.*

## Prime Numbers vs Composite Numbers

Prime numbers and composite numbers are two different types of numbers, and it is important to understand the differences between them.

Prime Numbers | Composite Numbers |
---|---|

Prime numbers are only divisible by 1 and themselves. | Composite numbers are divisible by more than two integers. |

Prime numbers have only two factors, 1 and themselves. | Composite numbers have more than two factors. |

Prime numbers are always odd, except for 2. | Composite numbers can be even or odd. |

Examples: 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 | Examples: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40 |

## Sieve of Eratosthenes

Sieve of Eratosthenes is a popular algorithm that generates all prime numbers smaller than or equal to a given number. The algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with 2.

The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them equal to that prime.

## Example:

Here is an example of “Sieve of Eratosthenes” program in C#.

```
using System;
class SieveOfEratosthenes
{
static void Main()
{
int n = 100;
bool[] prime = new bool[n + 1];
// Initialize all elements of boolean array to true
for (int i = 0; i <= n; i++)
{
prime[i] = true;
}
// Mark all multiples of 2 as composite
for (int p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (int i = p * 2; i <= n; i += p)
{
prime[i] = false;
}
}
}
// Print all prime numbers
Console.WriteLine("Prime numbers from 1 to " + n + " are:");
for (int p = 2; p <= n; p++)
{
if (prime[p] == true)
{
Console.Write(p + " ");
}
}
}
}
```

**Output:**

```
Prime numbers from 1 to 100 are:
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
```

## Goldbach’s Conjecture

This is a conjecture that every even integer greater than 2 can be expressed as the sum of two primes. Although it has not been proved or disproved, it has been tested extensively for all integers up to 4 Ã— 10^18.

**Example:** The even integer 36 can be expressed as the sum of two prime numbers as 31 + 5.

## Prime Factorization

Prime Factorization involves finding the factors of a number that are prime numbers. Every positive integer can be uniquely represented as a product of primes up to the ordering of the factors.

**Example:** The prime factorization of 84 is 2 * 2 * 3 * 7.

## Mersenne Primes

Mersenne Primes are prime numbers that can be written in the form 2^p – 1, where p is also a prime number.

Example: 3, 7, 31, 127, 8191, 131071, etc. are Mersenne primes.

## Twin Primes

These are pairs of prime numbers that differ by 2.

Example: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), etc., are twin primes.

## FAQs

### Q: What are prime numbers?

Prime numbers are numbers that are only divisible by 1 and themselves. Examples of prime numbers include 2, 3, 5, 7, 11, and so on.

### Q: Why are prime numbers important?

Prime numbers are important in mathematics and computer science because they have unique properties and can be used in various algorithms and encryption techniques. For example, the RSA encryption algorithm relies heavily on using large prime numbers.

### Q: How can I generate a list of prime numbers?

We can use several algorithms to generate a list of prime numbers. Some popular algorithms include the Sieve of Eratosthenes, the Sieve of Sundaram, and the Miller-Rabin primality test.

### Q: What is the difference between prime and composite numbers?

Prime numbers are numbers that are only divisible by 1 and themselves, whereas composite numbers are numbers that have more than two factors. For example, 4 is a composite number because it is divisible by 1, 2, and 4.

### Q: How can I check if a number is prime or composite?

One way to check if a number is prime or composite is to factorize it and count the number of factors. If the number has more than two factors, it is composite; otherwise, it is prime.

However, for large numbers, this method can be computationally expensive. Other algorithms, such as the Miller-Rabin primality test, can efficiently test if a number is prime or composite.

### Q: What is the time complexity of the Sieve of Eratosthenes algorithm?

The time complexity of the Sieve of Eratosthenes algorithm is O(n*log(log(n))) where n is the upper limit of the range of numbers being checked for primality. That makes it one of the most efficient algorithms for generating a list of prime numbers.

### Q: Can the Sieve of Eratosthenes algorithm be parallelized?

Yes, the Sieve of Eratosthenes algorithm can be parallelized to take advantage of multi-core processors and improve its performance.

That is because each iteration of the algorithm is independent of the others, so it can be divided into multiple threads that execute simultaneously.

*References: Byjus-Prime Numbers*

**Articles you might also like:**

- Different Ways to Calculate Factorial in C# (with Full Code Examples)
- Fibonacci sequence: Fibonacci series in C# (with examples)
- Program to Convert Fahrenheit to Celsius: Algorithm, Formula, and Code Examples
- Converting Celsius to Fahrenheit in C#

- CTE in SQL Server: Learn Common Table Expressions with Examples - September 14, 2023
- Garbage Collection in C#: Managing Memory Efficiently - September 13, 2023
- Static vs Singleton in C#: Understanding the Key Differences - September 6, 2023