I am struggling to write the code to find the prime numbers from given set of numbers.
Can someone help me out with the logic to find the prime numbers say from 1 to 100! I have seen many codes but I do not quite understand their logic.
I am struggling to write the code to find the prime numbers from given set of numbers.
Can someone help me out with the logic to find the prime numbers say from 1 to 100! I have seen many codes but I do not quite understand their logic.
What algorithm do you have in mind, or least what algorithms do you know of to determine prime numbers or find prime numbers in a range?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
It certainly is possible. Read up on trial division. With this approach, you would check each number in the range for primality.Originally Posted by shan2014
Another method may be more applicable to your particular scenario: read up on the sieve of Eratosthenes.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Why do you say that it led you to a dead end?Originally Posted by shan2014
What is the code that you wrote to implement it and how does it not work?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Dead end as in I couldn't get me to incorporate the logic in the code? My little drops of knowledge in C is a hurdle!!
So as of now I am stuck here
Code:main() { float a,b,n,i,j,k; printf("Enter two positive numbers a and b");// these will be my set of numbers scanf("%f %f",&a,&b); for(i=a;i<=b;i++) {
Are you stuck with writing the code, or stuck with understanding the algorithm?Originally Posted by shan2014
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Simplify: for example, assume that a = 1 and b = 30, so as to skip the input step. Next, implement the sieve on paper using those example input, that is, write down the integers in the range [1, 30], and cross them out according to the algorithm, and finally extract the prime numbers in the range. Having done that, what data structure would you need to implement the sieve as a program?Originally Posted by shan2014
By the way, you are dealing with integers here, so why use the float data type?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Look up the modulus operator "%".
Tim S.
"...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson
Oh! I was trying something that's why i was using float.
Anyway this is my interpretation of the Sieve . but am getting the multiples of 5?
Code:int a,b,i,j,flag; printf("Enter two positive numbers:"); scanf("%d%d", &a,&b); for(i=a;i<=b;i++) { flag=0; for(j=2;j<=i/2;j++) {if(i%j==0) flag=1; break;} if(i!=1 && i==2 && flag==0) printf("%d ",i); else if(i!=1 && i==3 && flag==0) printf("%d ",i); else if(i!=1 && i==5 && flag==0) printf("%d ",i); else if(i!=1 && flag==0) printf("%d ",i); } getch(); return 0;
That's not even close to an interpretation of the Sieve of Eratosthenes. It's actually more like a broken implementation of trial division.
The sieve works by recording prime values that have been found, using them to test subsequent values, and (when a new prime is found - i.e. a value is found for which no previous prime is a factor) adding it to the list of recorded primes. Nowhere in your code is there some means of keeping track of what primes have been found, let alone using them.
What you need to do is read the description of the sieve, and then work through a few examples by hand BEFORE trying to write code.
Also, it is only necessary to check for factors up to square root of a value, not to half that value (if there is any prime factor of a value n, one is always less than the square root of n). Caution though: a common beginner mistake, when told that, is to use floating point functions (sqrt(), pow()) to compute the square root. Instead, look up code for "integer square root" (which does everything using integers, and is not subject to rounding errors or other problems associated with floating point).