Finding prime numbers

This is a discussion on Finding prime numbers within the C Programming forums, part of the General Programming Boards category; Hi, I wrote a code to check all the primes between 2 and 1002, but I for each nth number ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    114

    Finding prime numbers

    Hi, I wrote a code to check all the primes between 2 and 1002, but I for each nth number tested, I go from 2 to n-1. By running the program, I got 168 numbers, which is correct according to a website. However, I've read it that I only need to check until the square root of n, but I tried making that change in the inner for loop by choosing j < sqr(i), and it just finds the number 2 as a prime. Why is this happening? Thanks in advance!

    Code:
    #include <stdio.h>
    #include <math.h>
    
    void primeFinder(void);
    
    int main(void)
    {
        printf("Prime numbers from 1 to 1000:\n\n");
        primeFinder();
    
        return 0;
    }
    
    
    void primeFinder(void)
    {
        int i;
        int j;
        int k;
        int n_primes = 0;
    
        //i is the number to be tested:
        for ( i = 2 ; i <= 1000 ; i++ )
        {
            //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
            for ( j = 2, k = 0 ; j < i ; j++ )
            {
                //i is not prime, whatever is the value of j:
                if ( i % j == 0 )
                {
                    //If remainder is 0, there is no need to test that i anymore:
                    break;
                }
                else
                {
                    k++;
                }
    
            } //End of inner for
            //i is prime:
            if ( k == i - 2 )
            {
                printf("%d\t", i);
                n_primes++;
            }
        } //End of outer for
        printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,157
    I tried making that change in the inner for loop by choosing j < sqr(i), and it just finds the number 2 as a prime. Why is this happening?
    Look carefully at the condition by which you finally decide whether to print the number as prime:
    Code:
    if ( k == i - 2 )
    Does it tally with your introduction of sqrt(i)?

    By the way, why do you need k when you already have j?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,636
    Take i = 49 for an example. 7*7 = 49, so it's composite. But if you only check j < sqrt(i), you only check divisors from 2 through 6, which would incorrectly report 49 as prime. You need to go until j <= sqrt(i).

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    114
    Thanks, laserlight and anduril462. I've now managed to improve the program by checking only until the square root of each number.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Prime Numbers
    By alireza beygi in forum C Programming
    Replies: 2
    Last Post: 01-13-2012, 04:06 AM
  2. non prime numbers or composite numbers program.help plz!
    By danishzaidi in forum C Programming
    Replies: 10
    Last Post: 11-15-2011, 11:10 AM
  3. Replies: 2
    Last Post: 12-24-2009, 02:41 AM
  4. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 12:12 PM
  5. Finding and Printing prime numbers using arrays
    By Sektor in forum C++ Programming
    Replies: 5
    Last Post: 12-11-2003, 08:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21