Almost prime numbers

Question

Almost prime numbers

Navigation

#1 by (4 votes)
#2 by (2 votes)

4

I have a question in C, I know if a number is cousin, but almost cousin do not know .. how do I do?

Follow the part of the code working! However, just checking to see if it's cousin .. the almost cousin does not spin

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

}

c

asked by anonymous 12.09.2017 / 19:49

2 answers

2

Your problem is that at first if the condition is (controle == 2) . Soon, it will always go in there and will never enter else if (controle == 2 && controle*controle == num) because if the control is 2, it will already go to the first condition.

To resolve this issue, try reversing 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);
}

12.09.2017 / 19:55

How to consume this JSON with JavaScript? How to update all records of all tables that have FK from a table

score 4 · Accepted Answer

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

15 = 3 * 5 is 2-quasi-prime,
9 = 3 * 3 is 2-quasi-prime,
16 = 2 * 2 * 2 * 2 is 4-quasi-prime,
5 = 5 is 1-quasi-prime.

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

For this, we have to find out what the prime factors are and how often they are used in each number. Its algorithm is very close to the detection of a k -quasi-primo number. I will adjust in such a way that the value of k indicates which " degree " of quasi-primality the number n has:

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

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

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