4

Tenho uma duvida em C, eu sei verificar se um numero é primo, porém, quase primo não sei.. como eu faço?

Segue a parte do código funcionando! Porém, só verificando se é primo.. o quase primo não roda

//  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!");

}
17
  • 1
    Isso, nenhum deles são! Commented 12/09/2017 às 18:06
  • 2
    Aqui diz que 16 é quase primo (para k=4) @JeffersonQuesado
    – bfavaretto
    Commented 12/09/2017 às 18:08
  • 1
    @Jefferson E eu então? Nunca tinha ouvido falar em "quase" primos até agora. Não boto a mão no fogo pelo que está na Wikipedia, nem entendi totalmente.
    – bfavaretto
    Commented 12/09/2017 às 18:12
  • 1
    Um numero quase primo, ou semi primo, é aquele que é o produto de dois números primos. Por exemplo 4, 6, 9, etc... (2*2, 2*3, 3*3) Commented 12/09/2017 às 18:12
  • 1
    @Cleber Então seria o que diz a Wikipédia limitado a k=2?
    – bfavaretto
    Commented 12/09/2017 às 18:13

2 Respostas 2

4

Um número k-quasi-primo é dado por ele ser composto por um produto de primos com k fatores. Exemplos:

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

No caso, o conceito quase primo é equivalente a 2-quasi-primo. Ou seja, k = 2.

Para isso, temos de descobrir quais são os fatores primos e quantas vezes eles são usados em cada número. Seu algoritmo está muito próximo da detecção de um número k-quasi-primo. Vou ajustar de tal modo que o valor da variável k indica qual "grau" de quasi-primalidade o número n possui:

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

No caso, para detectar com quasi-primalidade k=2, basta verificar se k é 2 no final da execução. Também podemos abortar o laço antes da sua conclusão, caso se detecte um novo fator primo e k já valer 2, podemos retornar falso. Desse jeito:

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);
}
1

Seu problema é que no primeiro if a condição é (controle == 2).
Logo, ele sempre vai entrar ali e nunca vai entrar no else if (controle == 2 && controle*controle == num) porque se o controle for 2, ele já vai para a primeira condição.

Para resolver este problema, tente inverter as condições:

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);
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .