Thread: C code to find the prime numbers from given set of numbers?

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.

Originally Posted by laserlight

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?

I am just trying to apply the basic mathematical concepts of the prime numbers i.e., divisible only by the number and one. But it just doesn't seem possible???

Originally Posted by laserlight

It certainly is possible. Read up on trial division. With this approach, you would check each number in the range for primality.

Another method may be more applicable to your particular scenario: read up on the sieve of Eratosthenes.

I actually tried the Sieve of Eratoshthenes.. but led to a dead end??

Originally Posted by laserlight

Why do you say that it led you to a dead end?

What is the code that you wrote to implement it and how does it not work?

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++)
        {

Originally Posted by laserlight

Are you stuck with writing the code, or stuck with understanding the algorithm?

i am stuck with the code.. on how to implement the algo!!

Originally Posted by laserlight

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?

By the way, you are dealing with integers here, so why use the float data type?

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;

Originally Posted by grumpy

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).

hahaha .. thank you for the correction. My limited knowledge of C programming leads to such a outcome! Anyway inorder to record the primes that have been found I would need to make an array right!

Hodor hardcodes all prime numbers into his source