-4

I am trying to generate a list of all the prime numbers for the first 1000 numbers.

I am not sure where I am going wrong in my code. From what I can tell, my nested for loop is not reading dividing/reading the array correctly and then assigning that array the proper value. How can I fix it?

The program currently only generates all the odd numbers.

int main() {
    int x = 1;
    int arr[500];
    int i, j, k;
    int counter;
    int primearray[500];

    for (j = 0; j <= 500; j++) {
        x += 2;
        arr[j] = x;

        for (k = 1; k <= 15; k++) {
            counter = x % k;
            if (counter == 0) {
                primearray[j] = x;
            } else {
                break;
            }
        }

        for (i = 0; i < 500; i++) {
            printf("%d ", primearray[i]);
    }
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
Jack
  • 1
  • 1
  • google with the subject of this question – sunkuet02 Oct 23 '16 at 12:06
  • 2
    Please choose a language - I guess you are using C – Ed Heal Oct 23 '16 at 12:07
  • 1
    Your indentation (is) was misleading — it's easy to read your code wrong because of that. Your printing loop is in the wrong place; it should be after the main loop, not within it. Don't forget to print newlines. You shouldn't be printing 500 numbers; there are only 168 prime numbers less than 1000 (starting 2, 3, 5, 7, 11, 13, 15, 17, … up to 971, 977, 983, 991, 997). The factor of 15 is puzzling. You should probably look up [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). – Jonathan Leffler Oct 23 '16 at 16:26
  • The code as posted will not compile. There are 6 `{`s and 5 `}`s. – Peter Mortensen May 22 '22 at 14:31

3 Answers3

3

Please invest time in learning how to indent your code. Choose a style that suits you and use it consistently: this will make your programs easier to read, and in turn easier to understand.

As I'm writing this, your posted code doesn't even compile because a closing curly brace } is missing: such editing mistakes are made possible by misleading indentation. Also note that in a properly written C program you must remember to #include any standard headers that are used:

#include <stdio.h> // for `printf()`

Rather than try to fix your algorithm, which at first glance doesn't make any sense to me anyway, I will try to help you restructure your program.

Keep main() simple

Given that the goal of your program is checking which of the first 1000 natural numbers are prime, the main() function should do no more than loop through those numbers and print the ones which are prime, like this:

for (int n=0; n < 1000; ++n)
    if (is_prime(n))
        printf("%d\n", n);

Putting them in an array instead of printing is equally easy:

int prime_array[500];   // array of primes
int k=0;                // current index in array of primes

for (int n=0; n < 1000; ++n)
    if (is_prime(n))
        prime_array[k++] = n;

Break up the program in several functions

In accordance to the previous idea, write short and simple functions that do one thing, and do it well. In your case, you should write the is_prime() function to determine if a number is prime or not. You can start from here:

///
/// @brief Checks if a number is prime.
/// @param [in] n       Number to be checked
/// @returns Whether `n` is prime or not.
/// @retval 1           If `n` is prime.
/// @retval 0           If `n` is not prime.
///
int is_prime(int n)
{
    // TODO: add code here
}

Decide how to check for primality

There is a Primality test article on Wikipedia that you should read.

First, you must correctly handle these special cases:

  • 0 is not prime
  • 1 is not prime
  • 2 is prime
// TODO: also check 1 and 2 in a similar fashion
if (n == 0)
    return 0;

After this is done, you can use a naive and inefficient algorithm that checks the other numbers:

// try divisors from 2 to n-1
for (int d=2; d < n; ++d)
    if (n % d == 0)     // if the division was even,
        return 0;       // the number is not prime

return 1;               // if we get here, the number is prime

If you want to use a faster (but more complicated) algorithm for checking primes, look back at the Wikipedia article linked above. Notice how you'd only have to change the code inside is_prime() and the rest of the program would work the same, unchanged.

user7023624
  • 571
  • 5
  • 14
  • 1
    The 'one step less naïve' algorithm only checks values such that `d * d <= n`, effectively only testing values up to the square root of N. That makes a measurable difference to the performance, even if you're only finding primes less than 1000 (a factor of 10, roughly: 260 µs vs 26 µs). – Jonathan Leffler Oct 23 '16 at 16:50
0

As I understood from your code, arr is an array of possible candidates and primearray is an array of approved ones. No every candidate will be approved one so you need different variables for indexing them.

The second issue is the algorithm for approving candidates. From this part of your code (I changed some indents)

for (k = 1; k <= 15; k++) {
    counter = x%k;
    if (counter == 0) {
        primearray[j] = x;
    } else {
        break;
}

follows that you approve a candidate if it is divisible by all integers from 1 to 15 - I am sorry but prime numbers have not this property.

MarianD
  • 13,096
  • 12
  • 42
  • 54
-1

I think you could refer to this code which will generate all prime numbers up to the number that you specify. I think this will be more optimised.

void main()
{
    int n, i, j, temp=0;
    printf("Enter a number \n");
    scanf("%d", &n);
    printf(" Prime numbers -\n");

    for(i=2; i<n+1; i++)
    {
        temp = 0;

        for(j=2; j<i; j++)
        {
            if(i%j == 0)
            {
                temp = 1;
                break;
            }
        }

        if(temp == 0)
        {
            printf("%d \n", i);
        }
    }
    getch();
}
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Vishnu Rahul
  • 31
  • 5