471,316 Members | 1,056 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,316 software developers and data experts.

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

//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;
}
Apr 23 '17 #1
2 1078
weaknessforcats
9,208 Expert Mod 8TB
I don't think your algorithm works.

Prime numbers are numbers that are the product of themselves and 1. Saying it another way, the only factors of a prime number are the prime number itself and 1. Nothing about division, square roots, etc.

The code says:
Expand|Select|Wrap|Line Numbers
  1. //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.
All numbers are divisible by prime numbers since all numbers are divisible by 1. All even numbers are divisible by 2.

You have to write a loop that tests a given number to be prime. It would divide the number by all numbers from 2 to the number itself. The number is prime if the only non-zero quotient is 1 by using the number itself.
Apr 23 '17 #2
donbock
2,425 Expert 2GB
I suggest you look at The Sieve of Erasthones. It is a method for accomplishing your goal that doesn't require any division.
Apr 24 '17 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

13 posts views Thread by Don | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.