Almost prime numbers

Question

I have a doubt in C, I know check if a number is prime, however, almost cousin do not know.. as I do?

Follow the part of the code working! However, just checking if it is prime.. the almost prime does not run

//  quasePrimos.c
// 
//
//  Created by Braynner Teixeira on 12/09/17.
//  Copyright © 2017 Braynner Teixeira. All rights reserved.
//


#include <stdio.h>

int main(){

    int num, i, controle=0;


    printf("Informe um numero: ");
    scanf("%d", &num);

    if (num > 1)
    {


         // Dividir o numero informado por todos os numeros que estao entre ele e 1.

        for (i = 1; i <= num; i++)
        {

            if (num % i == 0) 
            controle++;

        }


           if (controle == 2) {


            printf("O numero %d e um numero primo!\n", num);


        }
        else if (controle == 2 && controle*controle == num) {

                printf("O numero %d e quase primo!\n", num);

            }else {

            printf("O numero %d nao e um numero primo!\n", num);
        }

    }

    else if (num == 1 ) printf("O numero nao é primo e nem quase primo!");

}

Answer 1

A number k-quasi-primo is given because it consists of a product of primes with k factors. Examples:

• 15 = 3 * 5 is 2-quasi-primo,
• 9 = 3 * 3 is 2-quasi-primo,
• 16 = 2 * 2 * 2 * 2 is 4-quasi-cousin,
• 5 = 5 is 1-quasi-primo.

In this case, the quasi-prime concept is equivalent to 2-quasi-prime. I.e., k = 2.

To do this, we need to find out what the prime factors are and how often they are used in each number. Your algorithm is very close to the detection of a number k-quasi-primo. I will adjust so that the value of the variable k indicates which "degree" of quasi-primality the number n possesses:

int k = 0;
int i = 2;
while (n > 1) {
 while (n % i == 0) {
   k++;
   n /= i;
 }
 i++;
}

In case, to detect with quasi-primality k=2, just check to see if k is 2 at the end of the run. We can also abort the loop before its completion if a new prime factor is detected and k already worth 2, we can return false. That way:

int num = n; // como vou deteriorar o valor de n, vou guardar uma cópia para futura impressão
int quasi_primalidade = 2;
int k = 0;
int i = 2;
while (n > 1) {
 while (n % i == 0) {
   k++;
   n /= i;
   if (k > quasi_primalidade) {
     // pode ser um return se estiver em uma função
     goto FIM_LACOS;
   }
 }
 i++;
}
FIM_LACOS:
if (k == quasi_primalidade) {
  printf("O numero %d e um numero primo!\n", num);
} else {
  printf("O numero %d nao eh um numero primo =(\n", num);
}

Answer 2

Your problem is that in the first if condition is (controle == 2).
Soon, he’ll always go in there and never get into the else if (controle == 2 && controle*controle == num) because if the control is 2, it already goes to the first condition.

To solve this problem, try to reverse the conditions:

if (controle == 2 && controle*controle == num) {
    printf("O numero %d e quase primo!\n", num);
}
else if (controle == 2) {
    printf("O numero %d e um numero primo!\n", num);
}
else {
    printf("O numero %d nao e um numero primo!\n", num);
}