# Program to Generate Prime Numbers between 1 to n

View: 388    Dowload: 0   Comment: 0   Post by: hanhga   Category: Php&mySql   Fields: Other

Write an efficient program to generate prime numbers between 1 to n. Program to print prime number between 1 to n. It is one of the most asked interview questions in interviews.

In this article, i will discuss most efficient algorithm to generate Prime Numbers. Before solving this program let’s understand what is prime number.

What is Prime Number

A prime number is a whole number, whose only two factors are 1 and itself.

For example – 2, 3, 5, 7, 11 etc. are prime numbers. 2 is the only even prime number.

There are multiple ways you can generate prime numbers but the most efficient algorithm for generating prime number is Sieve of Eratosthenes.

The time complexity of this algorithm is O(n log logn).

Implement stack using array

## Sieve of Eratosthenes Algorithm

Suppose we have to print prime numbers between 1 to 20.

1. First generate a list of integers from 2 to 20:

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

2. First number in the list is 2; cross out every multiple of 2.

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

So following numbers are cross-out. 4  6  8  10  12  16  18  20

3. Next number is 3 cross out every multiple of 3.

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Continue like this. At the end, numbers which are not cross out are prime numbers.

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

So the prime numbers between 1 to 20 is

Let’s implement Sieve of Eratosthenes algorithm through code.

## PHP Program to Generate Prime Numbers between 1 to n

Here is PHP sample code for the implementation of Sieve of Eratosthenes algorithm.

```/* Generate Prime number */
function generatePrime(\$n){
/* Declare prime as an array. */
\$prime = array();
/* Mark the value of all element as Zero . */
for(\$i = 1; \$i <= \$n; \$i++){
\$prime[\$i] = 0;
}
\$k=2;
\$mul = 0;
while(\$k < \$n){
for(\$j = 2 ; \$n >= \$k*\$j; \$j++){
\$mul = \$j * \$k;
/* Cross-out multiple of a number. */
\$prime[\$mul]=1;
}
\$k++;
}
for(\$i = 2; \$i <= \$n; \$i++){
/* Those who marked zero are prime numbers. */
if(\$prime[\$i] == 0)
echo "\$i\n";
}
}
generatePrime(20);```

## C Program to Generate Prime Numbers between 1 to n

```#include <stdio.h>

int main() {
int num,i,prime[100],k=2;

printf("Enter number (less than or equal to 100) \n");
scanf("%d",&num);

for(i = 2; i <= num; i++){
prime[i] = 0;
}

while(k < num){
for(i = 2; num >= k*i; i++){
/*Marked multiple of number as 1. */
prime[k*i]=1;
}
k++;
}

for(i = 2; i <= num; i++){
if(prime[i] == 0){
printf("%d\n",i);
}
}
return 0;
}```

Write an efficient program to generate prime numbers between 1 to n. Program to print prime number between 1 to n. It is one of the most asked interview questions in interviews.

Posted on 23-09-2016

#### Comment:

To comment you must be logged in members.

## Files with category

• ### SimpleXML is a PHP extension that allows us to easily manipulate and get XML data

Category: Php&mySql     Fields: none

SimpleXML provides an easy way of getting an element's name, attributes and textual content if you know the XML document's structure or layout. SimpleXML turns an XML document into a data structure you can iterate through like a collection of arrays...

Category: Php&mySql     Fields: Other

This is my favorite PHP download script. I’ve used a different more simple method until a client wanted to be able to allow their site visitors to download a large file from a password protected directory. The PHP script works on Apache web servers...

• ### Installing OCI8 & PHP 7.2 on RHEL or CentOS 6

Category: Php&mySql     Fields: Other

You’ll need to stop Apache (web server) using the following command. In any Linux commands I show in this article, it presumes you aren’t logged in as the root user, so you will need to use sudo to issue privileged commands.

• ### PHP source code: get content of google search

Category: Php&mySql     Fields: Other

How to get the results of google search and display on your website. This PHP code can do that. Refer to the following code.

• ### PHP as a Scripting Language for C#

Category: Php&mySql     Fields: none

When creating .NET applications (including desktop and web applications), it may be useful to allow extending the application using some scripting language. The users of the application can write simple scripts to configure the application, modify...

• ### How to Picking the Brains of Your Customers with Microsoft’s Text Analytics

Category: Php&mySql     Fields: Other

With the explosion of machine learning services in recent years, it has become easier than ever for developers to create “smart apps”. In this article, I’ll introduce you to Microsoft’s offering for providing machine-learning capabilities to apps.

• ### How to MySqli Tutorial PHP MySqli Extension

Category: Php&mySql     Fields: Other

PHP provides three api to connect mysql Database.

• ### Make Laravel Artisan Commands

Category: Php&mySql     Fields: Other

Artisan is the command line tool used in Laravel framework. It offers a bunch of useful command that can help you develop application quickly. Apart from Artisan available commands, you can create your own custom commands to improve your workflow.

File suggestion for you
• Joomla template - 1805 view Blogus Free is a responsive Joomla! 3 template, based on the Bootstrap Framework. The Bootstrap Framework makes it fully responsive to all screen...

• Web Development - 1541 view I have recently realised how folks get significantly uncomfortable and could also loose little amount of productivity speed when navigating Solution...

• WordPress template - 405 view Fossile WordPress theme is a 2 columns fixed width CSS3/HTML5 Responsive WP template by Codetitle. This theme has theme options, featured content and...

• Php&mySql - 442 view Back in January, I made it one of my New Year’s resolutions to walk 4000 kilometers for the sake of fitness. I’ve been documenting this virtual...

• Javascript - 457 view Regular expressions use special (and, at first, somewhat confusing) codes to detect patterns in strings of text. For example, if you’re presenting...

Mega tags
• Php&mySql - 596 view Optical Character Recognition (OCR) is the process of converting...

• Php&mySql - 15756 view If your website allows users to upload photos, image cropping/resizing...

• Php&mySql - 381 view If you’ve been using Git for more than a short length of time, you’ll...

• Icons - 1115 view Iconizer is a small utility that installs a system-wide hook to...

• Php&mySql - 475 view Task Management PHP MYSQL Source Code is a simple, simple to use,...

• HTML-CSS template - 288 view If you don’t like change, perhaps web development isn’t for you. I...