how to list all pairs of sexy primes-CodePudding

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)

CodePudding user response：

You can use Sieve to speed up the program. It can generate all pairs in O(N log N) time. Here's the Algorithm.

Now, you have a boolean array, is_prime where is_prime[i] is true if i is a prime, false otherwise.

Now, iterate from i = 1 to i = N and check if is_prime[i] && is_prime[i 6], if the condition is true, output the pair.

CodePudding user response：

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  )

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: