
April 23rd, 2017, 08:33 AM
#1
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

April 23rd, 2017, 08:40 AM
#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
Victor Nijegorodov

April 23rd, 2017, 08:41 AM
#3
Re: want to know the complexity of my program ,new way to find prime numbers
Sorry! The wrong link address!
The correct one is http://forums.codeguru.com/announcement.php?f=7
Victor Nijegorodov

April 23rd, 2017, 01:13 PM
#4
Re: want to know the complexity of my program ,new way to find prime numbers
Originally Posted by VictorN
sorry but i didn't get what you mean to say ,this is a new problem and i really need the answer .

April 24th, 2017, 04:07 AM
#5
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/SieveJFP.pdf
the complexity is Θ(n√n / (log n)^2).
Last edited by wolle; April 25th, 2017 at 11:39 PM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
