473,239 Members | 1,506 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,239 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 1299
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,426 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

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

Similar topics

13
by: Don | last post by:
> How do you write a program to print the prime numbers > up to 1 million? #include <stdio.h> /* This program implements a blindingly fast O(n^n) algorithm to find prime numbers, using an...
11
by: gchiazx | last post by:
Hi, can someone send me the algorithm for finding the products of prime numbers from a given number? Thank You Gary.
3
by: triplejump24 | last post by:
Hey. Im trying to make program that basically displays all the prime numbers. I need to use bool and for but im not quite sure if i have this right. So far i have this bunch of a mess but can...
3
by: aparna kulkarni | last post by:
i want to find out prime nos from 1 to 25 using do while loop.
4
by: Villanmac | last post by:
Hi i have made the following program to make a fucntion that determines if a number is prime. Than i am supposed to use this function to print all prime numbers between 1 and 10000. What am I...
8
by: cokofreedom | last post by:
I was reading up on this site http://www.noulakaz.net/weblog/ 2007/03/18/a-regular-expression-to-check-for-prime-numbers/] of an interesting way to work out prime numbers using Regular Expression....
6
by: ASIFSHEHZAD25 | last post by:
What is the minimum range of numbers which we need to go necessarily to check either a number is prime or not?(for all integers)
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...

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.