want to know the complexity of my program ,new way to find prime numbers
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: want to know the complexity of my program ,new way to find prime numbers

1. Junior Member
Join Date
Apr 2017
Posts
2

## want to know the complexity of my program ,new way to find prime numbers

Code:
```//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;
}```
Last edited by 2kaud; April 23rd, 2017 at 09:41 AM. Reason: Added code tags

2. ## Re: want to know the complexity of my program ,new way to find prime numbers

It would help if you used CODE tags around the code snippets and proper indentations within the code blocks!
Read also the Announcement: Before you post....: https://eu4.proxysite.com/process.ph...S0qA%3D%3D&b=1

3. ## Re: want to know the complexity of my program ,new way to find prime numbers

The correct one is http://forums.codeguru.com/announcement.php?f=7

4. Junior Member
Join Date
Apr 2017
Posts
2

## Re: want to know the complexity of my program ,new way to find prime numbers

Originally Posted by VictorN
The correct one is http://forums.codeguru.com/announcement.php?f=7
sorry but i didn't get what you mean to say ,this is a new problem and i really need the answer .

5. Member
Join Date
Feb 2017
Posts
209

## Re: want to know the complexity of my program ,new way to find prime numbers

Originally Posted by ujjawaltaleja
this is a new problem and i really need the answer .
Your algorithm is known as "trial division" (with primes as candidate factors). According to this paper (see page 4 about 10 lines from the bottom),

https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

the complexity is Θ(n√n / (log n)^2).
Last edited by wolle; April 25th, 2017 at 11:39 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

This a Codeguru.com survey!