Click here to Skip to main content
15,891,253 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
//simply we are going to use the approach that the numbers that are divisble by prime numbers are not prime and the others are prime.
#include<stdio.h>
#include<math.h>
int main()
{
	int n,i,arr[100000],size=0,j,temp;           // array is for storing prime numbers
	scanf("%d",&n);        // we will be finding prime numbers between 2 to n (both inclusive) 
	arr[0]=2;              // we know that 2 is a prime number
	size++;                // we got 1 prime number so size of array gets incremented  
	for(i=3;i<=n;i++)
	{
		temp=pow(i,0.5);       //square root of the number (for which we are going to check is it prime or not)
		for(j=0;arr[j]<=temp;j++){
			if(i%arr[j]==0)
			break;
		}
		if(arr[j]>temp)
		{
			arr[size]=i;
			size++;
		}
	}
	for(i=0;i<size;i++)
	printf("%d \n",arr[i]);
	return 0;
}


What I have tried:

i donot know much about complexity ,but i want to use this approach(if this way is efficient) in case of prime numbers related question in competitions
Posted
Updated 23-Apr-17 4:43am
Comments
Kornfeld Eliyahu Peter 23-Apr-17 8:27am    
https://primes.utm.edu/prove/merged.html
(Do you mean you found a new way of founding prime numbers? I do not think so... https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
Dave Kreskowiak 23-Apr-17 10:02am    
Ummm....that code doesn't find prime numbers. So what's the point of big O notation for this?

If you're using a Modulo operation on each number under test, you're doing it inefficiently.

Complexity of an algorithm means how the time and data or input are related, on a graph. Does the algorithm take more time as the data increases, or does it stay same, etc?

There is a notation, Big O notation (e.g. O(n)) that is used to demonstrate this. For your algorithm, I would recommend that you try it yourself, plot the time, data graph and then see if the graph increases or not. The function that is makes on the graph, is the complexity. This is the simplest way to find the overall complexity, because you can visualize it and then map it to the nearest mathematical function — log(n), n2, n etc.

For your help, here is a cheat sheet that you can use to check what complexity does that algorithm hold, Big-O Algorithm Complexity Cheat Sheet[^].

A complex way to find complexity can also be found here, How to find time complexity of an algorithm - Stack Overflow[^]
 
Share this answer
 
Quote:
but i want to use this approach(if this way is efficient) in case of prime numbers related question in competitions

I am sorry to say this but your approach is not efficient. It is even very naive.

The first thing that come to mind is an optimization to avoid even numbers testing because you already know '2' and no other even number is prime.
replace
C++
for(i=3;i<=n;i++)

with
C++
for(i=3;i<=n;i+=2)

Quote:
i donot know much about complexity

To get an idea of the O, you can do timing of your program and draw the curve and compare with known curves likes x, x^2, x^3


you should study some classical techniques:
Sieve of Eratosthenes - Wikipedia[^]
Sieve of Sundaram - Wikipedia[^] (after the name of an Indian mathematician)

Computational complexity of mathematical operations - Wikipedia[^]
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900