C++ Implementar função em C++

[alecounter]

Pessoal, tudo bem? alguém poderia por gentileza me indicar o erro deste algoritmo que verifica se o número é primo ou não? O erro é que a função só retorna true!

 

bool primo(int n) {
    for(int i = 2; i < int(sqrt(n)); i++)
        if(n % i == 0) return false;
    return true;
}

int main() {
    std::cout << primo(5);
}

 

[Ansi C]

O que acontece é que,  raiz-2 de 5 é menor que 3 e maior que 2: porém o valor 2 é retornado pelo casting~int;

Não satisfazendo a condição de i  <  2, pois i = 2.

[alecounter]

agora, AnsiC disse:

O que acontece é que,  raiz-2 de 5 é menor que 3 e maior que 2: porém o valor 2 é retornado pelo casting~int;

Não satisfazendo a condição de i  <  2, pois i = 2.

eu coloquei outra condição, fiz assim

 

for(int i = 2; i < n; i++)

e mesmo assim a coisa ainda não funciona!

[Ansi C]

9 minutos atrás, alecounter disse:

e mesmo assim a coisa ainda não funciona!

Só não funciona para 2, para os demais números naturais funciona.

 

[alecounter]

10 minutos atrás, AnsiC disse:

Só não funciona para 2, para os demais números naturais funciona.

 

por qual motivo isto está acontecendo?

[Ansi C]

Em 28/07/2018 às 13:36, alecounter disse:

eu coloquei outra condição, fiz assim

 

for(int i = 2; i < n; i++)

e mesmo assim a coisa ainda não funciona!

Estude o que é um número primo, mais seu algoritmo básico de primalidade: https://pt.wikipedia.org/wiki/Número_primo

 

 

[alecounter]

Eu já sei a definição de número primo. O que isso tem a ver com o problema?

adicionado 9 minutos depois

Problema resolvido. Uma pequena alteração no código resolveu o problema  estranho que na faculdade eu fiz a mesma coisa e não funcionou por lá... Lá na faculdade é Linux e aqui windows, será que tem algo a ver?

adicionado 17 minutos depois

3 horas atrás, AnsiC disse:

Só não funciona para 2, para os demais números naturais funciona.

 

se o meu número n for da forma n=2k, pra k natural, então deveria funcionar para o 2 também. o código não funcionou por algum motivo desconhecido, já que copiei e colei aqui no codeblocks em casa e tudo funcionou bem...

[Visitante]

@alecounter Aqui tem uma outra forma p usar em sua função p verificar se um número é primo:

#include <iostream>
using namespace std;

bool ehPrimo(int n) {

    int div = 0;

    for (int i = 1; i <= n; i++)
        if (n % i == 0) div++;

    return ((div == 2) && (n > 1));
}

int main() {

    for (int i = 0; i < 100; i++)
        if (ehPrimo(i))
            cout << i << " ";

    cout << endl;

    return 0;
}

Vê se entende a lógica usada, ok?

[Ansi C]

1 hora atrás, alecounter disse:

Eu já sei a definição de número primo. O que isso tem a ver com o problema

Tem tudo, @giu_d já demonstrou o quanto saber, e não pensar que sabe, é importante.

adicionado 5 minutos depois

1 hora atrás, alecounter disse:

código não funcionou por algum motivo desconhecido, já que copiei e colei aqui no codeblocks em casa e tudo funcionou bem..

Talvez porque 2 é o único primo par. Portanto 2%2 = 0 e ainda sim 2 é primo. Coisa que você só diz saber, e que explica o porquê de não funcionar exclusivamente com 2. 

[alecounter]

21 horas atrás, AnsiC disse:

Tem tudo, @giu_d já demonstrou o quanto saber, e não pensar que sabe, é importante.

adicionado 5 minutos depois

Talvez porque 2 é o único primo par. Portanto 2%2 = 0 e ainda sim 2 é primo. Coisa que você só diz saber, e que explica o porquê de não funcionar exclusivamente com 2. 

não amigo, eu simplesmente copiei o código que estava aqui no post no meu codeblock para windows e tudo funcionou bem. precisei apenas fazer uma alteração aqui:

for(int i = 2; i <= int(sqrt(n)); i++)

pois realmente não sabia que o valor de sqrt(n) seria truncado, pensei que fosse arredondado. Não sei o motivo pelo qual não funcionou no ambiente Linux onde estava anteriormente. Basicamente eu nem segui nada do que vcs disseram aqui

adicionado 2 minutos depois

21 horas atrás, giu_d disse:

 

Vê se entende a lógica usada, ok?

entendi a lógica sim, obrigado pelo algoritmo

como já disse, fiz uma alteração no código que fiz anteriormente e tudo funcionou bem

 

[Ansi C]

Então 0, 1 também são primos, pois ambos são naturais e menores que 2.

[alecounter]

1 minuto atrás, AnsiC disse:

Então 0, 1 também são primos, pois ambos são naturais e menores que 2.

aí é só tratar exceções... só colocar um if-else que leva alguns nanossegundos para ser computado

[Ansi C]

Em 28/07/2018 às 20:17, alecounter disse:

aí é só tratar exceções... só colocar um if-else que leva alguns nanossegundos para ser computado

Pois é, dependendo da máquina ambos os algoritmos têm o mesmo desempenho a com diferenças lógicas; é que o seu não trata as exceções , ou não tratava tratadas.

 

Beleza se acha que deve, post seu versão otimizada.

 

 

[alecounter]

não vejo outra alternativa a não ser usar exceções, em especial pelo caso n=0.

pelo algoritmo de euclides, se um número 'a' natural divide 0, então o quociente também é 0 e podemos escrever

0=0a. Percebe-se assim que qualquer valor contido no conjunto dos inteiros satisfaz isso, logo fica indeterminado. Contar divisores nesse caso não funciona(mesmo).

adicionado 2 minutos depois

algoritmo da divisão ***

[alecounter]

19 horas atrás, AnsiC disse:

pois é, dependendo da máquina ambos os algoritmos têm o mesmo desempenho. A diferença é que o seu não trata as exceções, ou não tratava. Beleza se acha que deve post seu versão otimizada.

a complexidade computacional dos algoritmos não é igual. no meu algoritmo, a decisão de o número 'n' ser um primo ou não se baseia no fato de algum número contido em {2,3,...,int(sqrt(n))} dividir n. Se isso acontecer, a função cospe a resposta imediatamente.

No caso do algoritmo do colega acima, o laço percorre o conjunto {1,2,...,n-1} em todos os casos e ainda itera sobre uma variável toda vez que ocorre uma divisão inteira. Podemos observar também que valores acima de int(sqrt(n)) nem precisariam ser verificados, pelo teorema fundamental da aritmética...

 

[Ansi C]

Completando para sirva de referência: No artigo do atalho no post#6 em que há uma perfeita definição de número primo e outras hiperligações. Entre descrito o algoritmo básico de primalidade: divisões sucessivas ou Crivo de Eratóstenes, para todos entenderem.

 

Assim eu entendo que:

Na sua forma mais ingenua: para se determinar um número primo (ou primalidade de um número inteiro) qualquer basta apenas testar se o inteiro natural é:

1. COMPOSTO: Um número composto, é o oposto ao número primo, é número fatorável: é divisível exato e por fatores primos.

 

O livro tudo em matemática 7 de matemática 0 (ou básica) ensina muito bem como fazer isso, em resumo:

• Basta verificar se o número tem raiz exata;
• Ou se é divisível por 2;
• Testar para todos valores ímpares de 3 até raiz-2 do número: é divisível exato- se sim: Daí não será primo.
• Nem todo número natural menor que 4 é primo: 0, e 1 não é primo.

 

 

Implementar função em C++

Spoiler

#include <cmath>
/*
 * primalidade de numero natural */
char esprimo (int numero){
  float raiz_numero;
  char sim = 1, nao = 0;
    if (numero < 2){return nao;} else
    if (numero < 4){return sim;} else
    if (numero%2 == 0){return nao;} else
    if (int (raiz_numero = sqrt (numero)) == raiz_numero){return nao;} else
    for (int k = 3; k < raiz_numero; k += 2){if (numero%k == 0){return nao;}}
  return sim;};

 

 

 

 

[Ansi C]

Muito simples, ingênua e bem implementada gostosa de se olhar!

Dúvidas?

[isrnick]

2 horas atrás, AnsiC disse:

ingênua

O que você quer dizer com ingênua? Inocente ou simples? E qual seria a versão não ingênua?