Search code examples
cprimes

how to list all pairs of sexy primes

How can i write a program that lists all sexy prime pairs that exist in n numbers.
For example if n = 10 the output should be (5, 11) and (7, 13)

My idea was to generate all primes within n and then add 6 to each and check if the i + 6 is a prime. But it doesnt work, there's no output and the program ends.

#include <stdio.h>

int main() {
    int i, j, n, k, isprime = 1, prime2, flag = 0;
  
    scanf("%d", &n);
          
    for (i = 3; i <= n; i++){
      for (j = 2; j <= i; j++){
        if (i % j == 0)
          break;
      }

      if (i == j){
        prime2 = i + 6;
        for (k = 3; k <= prime2; k++){
          if (prime2 % k == 0){
            flag++;
            break;
          }
        }

        if (flag == 0){
          printf("%d %d\n", i, prime2);
        }     
      }
    }

  return 0;
}

Any ideas of what im doing wrong or any tips on how to solve it? (with loops only)

Solution

  • As there're a lot of resources about finding a prime number, I'm not going to discuss that. Rather I'll try to point out the bug in your code.

    First problem:

    for (k = 3; k <= prime2; k++)

    Here you need to run the loop till prime2 - 1. Also you should start checking from 2 rather than 3, just like you did previously. That means,

    for (k = 2; k < prime2; k++)

    or

    for (k = 2; k <= prime2 - 1; k++)

    Reason: when k = prime2, prime2 % k will be 0. For finding out whether a number is prime we don't need to check if that number is divisible by 1 and that number itself.

    Note: Now you might think why the first prime number loop for (j = 2; j <= i; j++) is working .

    It's working because you've given an additional condition if (i == j) after it.

    Second problem:

    You need to declare the flag variable within the first loop.

    for (i = 2; i <= n; i++)
{
    int flag = 0;
    .... (rest of the code)
    ....
}

    Reason: Basically with the flag value, you're trying to find out whether prime2 is a prime number.

    Every time you'll get a prime number from the first loop, you'll have a new value of prime2. In your code, once you're incrementing the value of flag, you're never resetting the flag value.

    That's why once your code detects a prime2 which is not a prime, it'll never detect the second prime number again (prime2 which is actually prime).

    Overall code:

    #include <stdio.h>

int main()
{
    int i, j, n, k, isprime = 1, prime2;

    scanf("%d", &n);

    for (i = 3; i <= n; i++)
    {
        int flag = 0;    //  changing point
        for (j = 2; j <= i; j++)
        {
            if (i % j == 0)
                break;
        }

        if (i == j)
        {
            prime2 = i + 6;

            for (k = 2; k < prime2; k++)    //  changing point
            {
                if (prime2 % k == 0)
                {
                    flag++;
                    break;
                }
            }

            if (flag == 0)
            {
                printf("%d %d\n", i, prime2);
            }
        }
    }

    return 0;
}

    Few resources to know more about finding out prime numbers: