Prime numbers in C and is_prime

Question

I'm writing a program to find all of the prime numbers contained within a user input n. I am having trouble with the is_prime function.

#include <stdio.h>
#include <math.h>

main() {
  int n;
  int k;

  // gets user input for length of string
  // and stores it as n
  printf("Enter the value of n:");
  scanf("%d", &n);

  for (k = 2; k <= n; k++) {
    if (is_Prime(k) == 1) {
      printf("Printing primes less than or equal to %d: /n %d, &n, &k");
    }
  }

I want the output to look like this, but I am not sure how to print the list without using different variables for each prime number.

Printing primes less than or equal to 30:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.


    //here is the is_Prime function
    is_Prime (int n)
    {
    for(j = 2; j <= n/2; j++)
    {
    if(n%j != 0)
    {
    return 1;
    break;
    }
    }
    if(n%j == 0 )
    return 0;
    }

I am not sure how to call the is_prime subroutine? Any help?

You should read some good C programming book or site. Your `printf` is *very wrong* ! — Basile Starynkevitch, Feb 28 '15 at 20:30
Here's a [list of books](http://stackoverflow.com/a/562377/3386109) to help you get started. — user3386109, Feb 28 '15 at 20:37
is the is_prime function declared in a library that I have not called? — user56521, Feb 28 '15 at 21:01
No, the `is_prime` function is not a standardized library function, it's a function that you are meant to write. — user3386109, Feb 28 '15 at 21:03
Look at http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for a decent way to iteratively implement is_Prime(k) given n. — jschultz410, Feb 28 '15 at 21:13
how do you implement the subroutine so that it can be called in the loop — user56521, Feb 28 '15 at 23:41

score 1 · Answer 1 · answered Feb 28 '15 at 20:31

1

printf("Printing primes less than or equal to %d:\n", n);
for(k = 2; k <= n; k++)
{
    if(is_Prime(k) == 1)
    {
        printf("%d, ", k);
    }
}

answered Feb 28 '15 at 20:31

wyas

377
2
14

jschultz410 · Answer 2 · 2015-03-03T04:02:23.453

printf("Printing primes less than or equal to %d:\n%s", n, (n >= 2 ? "2" : ""));

for (k = 3; k <= n; ++k)
  if (is_Prime(k))
    printf(", %d", k);

printf("%s\n", (n >= 2 ? "." : ""));

Here's a slightly cleaner version of your is_Prime function:

int is_Prime(int n)
{
  if (n < 2)
    return 0;

  int last = (int) sqrt(n) + 1;  /* conservatively safe */

  for (int j = 2; j <= last; ++j)
    if (0 == n % j)
      return 0;

  return 1;
}

Note that you only really need to check up to the sqrt() of a number to find all its potential factors.

Also note that this is not a great way to find all the primes less than n, which is the prime purpose of your program, especially when you will repeatedly call this function incrementing n by 1 each time. I recommend trying to implement the Sieve of Eratosthenes or the Sieve of Sundaram instead -- so long as n isn't too large.

Prime numbers in C and is_prime

2 Answers2