Re: [ccppbrasil] Programa em c (números primos)

[Erle Carrara]

João,

Um número é primo se ele é divisível apenas por 1 e ele mesmo. Ou seja, se o resultado da divisão de um número por qualquer outro número que não seja ele mesmo nem 1 der resto igual a 0, ele não é primo. É exatamente isto que o código acima faz.

O código trata também o caso especial do número dois, que é primo. 2 é divisível por ele mesmo e 1,  e não seria "pego" no laço (só olhar o código pra entender).

Mas realmente tá meio confuso esse código, se for algum trabalho de faculdade recomendo gastar um tempinho pra dar uma melhorada nele!

(Outra dica, coloque o código no pastebin.com ou gist.github.com e mande só o link por email, fica mais fácil para todos verem porque mantém a indentação e colore o código de acordo com a syntax.)

Espero ter ajudado, 

Abraços!

Em 4 de maio de 2013 13:56, João Guilherme Silva <joaa...@gmail.com> escreveu:

A dúvida é o seguinte , meu colega me passou esse código, que serve pra identificar se um valor digitado pelo usuário é primo ou não .
Só que o problema é que eu não entendo porque o código funciona , sacam? Não consigo entender qual a lógica por trás do algoritmo .
Segue o código :http://www.mediafire.com/view/?c2o477ach484kbd
Desde já agradeço.

int main(void)
{
int n, c = 2;

printf("informe o valor:");
scanf("%d",&n);

for ( c = 2 ; c <= n - 1 ; c++ )
{
if ( n%c == 0 )
{
printf("numero composto");
break;
}
}
if ( c == n )
printf("numero primo");

system("PAUSE");	
return 0;
}

--
Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 
 
 

--
Erle Carrara

<carrar...@gmail.com>

[DQ]

Eu diria que este código é a solução óbvia (escrevi algo parecido a primeira vez que quis fazer isto).  Ele verifica se o número é primo testando se ele pode ser dividido por algum número entre 2 e n-1. Existem algumas otimizações bem simples: pense um pouco se precisa mesmo testar até n-1 e se precisa testar um por um.

Eu acho que vale a pena queimar um pouco os miolos nisto, simule o funcionamento com lápis e papel para alguns números pequenos. Mas você pode também dar uma procurada no google (até eu já escrevi um post no meu blog sobre o assunto).

DQ

[Marcio Gil]

Fun with prime numbers

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

Em 04/05/2013 13:56, Jo�o Guilherme Silva escreveu:
> A d�vida � o seguinte , meu colega me passou esse c�digo
> <http://forum.clubedohardware.com.br/#>, que serve pra identificar se um
> valor digitado pelo usu�rio � primo ou n�o .
> S� que o problema � que eu n�o entendo porque o c�digo funciona , sacam?
> N�o consigo entender qual a l�gica por tr�s do algoritmo .
> Segue o c�digo :http://www.mediafire.com/view/?c2o477ach484kbd
> Desde j� agrade�o.

[Marcio Gil]

O artigo que eu enviei na mensagem anterior mostra diversos m�todos de
busca de n�meros primos, cada vez mais eficiente.

Este que voc� enviou � o mais ineficiente poss�vel, pois simplesmente
procura algum n�mero entre 2 e n-1 que divida n, o que implica em n n�o
ser primo.

D� para melhorar um pouquinho, primeiro se n n�o for divis�vel por 2
n�o ser� divis�vel por nenhum par, ent�o s� precisa testar os �mpares.
Segundo que s� precisa testar at� a raiz quadrada de n, pois de c*c �
maior que n, ent�o n�o pode dividir n.

int main(void)
{
int n, c;

printf("Informe o valor:");
scanf("%d",&n);

if (n%2 == 0 && n != 2)
c = 2;
else
{
for (c = 3; c*c <= n; c+=2)
{
if (n%c == 0)
break;
}
}

if (n%c == 0)
printf("N�mero composto\n");
else
printf("N�mero primo\n");

system("PAUSE");

return 0;
}

Nota: c�digo n�o testado

Em 04/05/2013 13:56, Jo�o Guilherme Silva escreveu:
> A d�vida � o seguinte , meu colega me passou esse c�digo
> <http://forum.clubedohardware.com.br/#>, que serve pra identificar se um
> valor digitado pelo usu�rio � primo ou n�o .
> S� que o problema � que eu n�o entendo porque o c�digo funciona , sacam?
> N�o consigo entender qual a l�gica por tr�s do algoritmo .
> Segue o c�digo :http://www.mediafire.com/view/?c2o477ach484kbd
> Desde j� agrade�o.
>
> int main(void)
> {
> int n, c = 2;
>
> printf("informe o valor:");
> scanf("%d",&n);
>
> for ( c = 2 ; c <= n - 1 ; c++ )
> {
> if ( n%c == 0 )
> {
> printf("numero composto");
> break;
> }
> }
> if ( c == n )
> printf("numero primo");
>
> system("PAUSE");
> return 0;
> }
>

> --
> Antes de enviar um e-mail para o grupo leia:
> http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
> --~--~---------~--~----~---------------------------------~----------~--~----~
> [&] C & C++ Brasil - http://www.ccppbrasil.org/
> Para sair dessa lista, envie um e-mail para
> ccppbrasil-...@googlegroups.com

> Para mais op��es, visite http://groups.google.com/group/ccppbrasil

[Marcio Gil]

Opa! O meu algoritmo diz que 3 � um n�mero composto.

C�digo corrigido, mantendo o mais simples poss�vel:

#include <stdio.h>

int main(void)
{
int n, c;

printf("Informe o valor:");
scanf("%d",&n);

if (n%2 == 0)

c = 2;
else
{
for (c = 3; c*c <= n; c+=2)
{
if (n%c == 0)
break;
}
}

if (n%c == 0 && n != c)

printf("N�mero composto\n");
else
printf("N�mero primo\n");

getchar();
getchar();

return 0;

[Wesley Mesquita]

Testem se suas soluções são aceitáveis (resolvem mesmo o problema e são eficientes) em um corretor automático (desses que o pessoal usa para treinar para competições de programação), por exemplo http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=524 .

2013/5/5 Raimundo Rodrigues <ray.au...@gmail.com>

Oi,

Sou novo aqui, minha dica é para a logica do problema, seu contador não necessita ir até ao antecessor do numero inserido, basta ir só até a metade dele pois nenhum numero divisor será maior que sua metade.

Espero ter ajudado.

Raimundo 

Em sábado, 4 de maio de 2013 13h56min24s UTC-3, João Guilherme Silva escreveu:

A dúvida é o seguinte , meu colega me passou esse código, que serve pra identificar se um valor digitado pelo usuário é primo ou não .
Só que o problema é que eu não entendo porque o código funciona , sacam? Não consigo entender qual a lógica por trás do algoritmo .
Segue o código :http://www.mediafire.com/view/?c2o477ach484kbd
Desde já agradeço.

int main(void)
{
int n, c = 2;

printf("informe o valor:");
scanf("%d",&n);

for ( c = 2 ; c <= n - 1 ; c++ )
{
if ( n%c == 0 )
{
printf("numero composto");
break;
}
}
if ( c == n )
printf("numero primo");

system("PAUSE");	
return 0;
}

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com

Para mais opções, visite http://groups.google.com/group/ccppbrasil

--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 
 
 

--
Wesley Mesquita
Computer Engineer
http://www.wesleymesquita.com

[Erle Carrara]

Boa noite!

Trava brincando de fazer exercícios do SPOJ pra praticar pra maratona INTERFATEC e descobri que quando o problema envolve número primo e performance o negócio é mais embaixo.

Estava tendo que aplicar todas as dicas matemáticas que reduzem o número de passos + cache para as soluções serem aceitas. Daí tive a brilhante ideia de calcular em tempo de compilação o número usando meta-programação por template, a compilação vai demorar um pouco mais, mas nessas competições o que conta é só o tempo de execução mesmo.

Alguém aí mais experiente tem alguma bala de prata pra verificar números primos?

Abraços!

[Cristian Maruan]

Eu sei que um número é primo se ele é divisível pelo intervalo [2, raiz_quadrada(n)]

onde o conjunto são os primos anteriores :P

Acho que é um dos meios matemáticos mais otimizados

Cristian Maruan Bosin

Engenharia da Computação / UFPel

GACI - Grupo de Arquiteturas e Circuitos Integrados

Telefone: (53) 8107 4550

Lattes: http://lattes.cnpq.br/7907279286507623

E-mail: cmarua...@gmail.com & cmb...@inf.ufpel.edu.br

[Cristian Maruan]

Errata:

Eu sei que um número é primo se ele não é divisível pelos numeros no intervalo [2, raiz_quadrada(n)], onde o conjunto são os primos anteriores :P

Para esse modo, tu tem que saber os primos anteriores, entao podes usar alguma
logica que guarda os primos e os usa para achar o prox..

Se alguém conhecer algum meio mais eficiente, favor compartilhar :P

Abraços

Cristian Maruan Bosin

Engenharia da Computação / UFPel

GACI - Grupo de Arquiteturas e Circuitos Integrados

Telefone: (53) 8107 4550

Lattes: http://lattes.cnpq.br/7907279286507623

E-mail: cmarua...@gmail.com & cmb...@inf.ufpel.edu.br

[Уθя¡ςκ]

Fiz essa funçãozinha básica constexpr que pode ser útil na questão "em tempo de compilação":

http://stackoverflow.com/q/16869087/

Problema que parece que o tiro saiu pela culatra, esperando o aval pra ver se é um bug do clang mesmo (em -O3).

A função constexpr é calculada em tempo de compilação se passar um valor de tempo de compilação, literals, expressões com literals, etc, E, se rodar em nível -O2 vai ser em tempo de compilação. Em -O0 no GCC por exemplo, pra garantir a avaliação em tempo de compilação, é preciso retornar o valor pra uma variável que também seja constexpr.

Mais informações: http://isocpp.org/blog/2013/01/when-does-a-constexpr-function-get-evaluated-at-compile-time-stackoverflow

[Уθя¡ςκ]

Para recursões muitos profundas, não esquecer da flag (a mesma pra clang e gcc),

clang++ -O2 -ftemplate-depth-1200 -std=c++11 -stdlib=libc++ -lcxxrt -ldl print-primes.cpp -o print-primes

#include <iostream>

template<typename T>
constexpr T divisors(T n, T c) { return !c ? 0 : !(n % c) + divisors(n, c - 1); }

template<typename T>
constexpr bool is_prime(T n) { return divisors(n, n) <= 2; }

template<unsigned int n>
struct print;

template<> struct print<0> {};

template<> struct print<1>
{
    inline static void primes() { std::cout << 1; }
};

template<unsigned int n>
struct print
{
    inline static void primes()
    {
        print<n - 1>::primes();
        if(is_prime(n))
            std::cout << ", " << n;
    }
};

int main()
{
    print<1000>::primes();
    std::cout << std::endl;
}

[Уθя¡ςκ]

return divisors(n, n) <= 2; => return divisors(n, n / 2) + 1 <= 2;

[Erle Carrara]

E a questão dos números primos negativos? (Nunca entendi muito bem eles)

[Cristian Maruan]

Existe primo negativo?
Eu acho que não...


Sent from my Windows Phone

---

De: Erle Carrara
Enviada em: 01/06/2013 09:45
Para: ccppb...@googlegroups.com
Assunto: Re: [ccppbrasil] Re: Programa em c (números primos)

[Erle Carrara]

Cristian,

Existe sim!

Por definição um **número primo** é aquele que tem exatamente quatro divisores distintos. Já um **número natural primo** tem exatamente 2 divisores distintos. 

E sempre desconfie da entrada dessas maratonas, se estiver escrito só "número primo" no enunciado por sim ter algum negativo ali no meio pra atrapalhar.

[]'s

Erle Carrara

<carrar...@gmail.com>

[Thiago Sonego Goulart]

Esse negócio de "número natural primo" tu viu da Wikipedia, mas a mesma página em inglês (muito mais completa) nem menciona números negativos. O mais importante é entender que problemas de maratona são feitos por pessoas diferentes, que muitas vezes não são experts. Considerando problemas de primos, alguns problemas são simplistas, com entradas > 1, enquanto outros vão colocar números negativos só para tentar pegar pessoas que não leem os enunciados detalhadamente (eu até já vi problema onde era pra assumir que 1 era primo!). Tenta fugir da segunda categoria. Isso vale pro problema que foi postado aqui antes, ele tem mais de 10 anos e o estilo dos problemas mudou bastante desde então.

--

Thiago Sonego Goulart

2013/6/1 Erle Carrara <carrar...@gmail.com>

[Уθя¡ςκ]

O seguinte tem mais otimizações e dicas sobre controle e correto uso de constexpr pra compile-time (anteriormente só tinha mencionado a opção pro controle de template-depth).

Basicamente o algoritmo segue a linha (para valores maiores que 2): É divisível por 2? então não é primo, pára recursão; Não é divisível? então só é preciso verificar divisores até no máximo 1/2 do número. É divisível por 3? então não é primo, pára recursão; Não é divisível? então só é preciso verificar divisores até no máximo 1/3 do número... e assim vai, se não for encontrado divisor e a verificação estiver passando do máximo e não for divisível por ele, é primo.

clang++ -O3 -ftemplate-depth-10000 -fconstexpr-depth=1024 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes.cpp -o compile-time-primes

#include <limits>
#include <iostream>
#include <cinttypes>

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return limit <= 1
           ? true
           : counter >= limit && number % limit
                ? true
                : number % counter
                    ? is_prime(number, number / counter, counter + 1)
                    : false;

}

template<typename T>
constexpr bool is_prime(T n)
{

    return n <= 1 ? false : is_prime(n, n / 2, T{2});
}

template<std::uint64_t n>
struct print_below;

template<> struct print_below<2> { inline static void primes() { std::cout << 2; } };
template<std::uint64_t n>
struct print_below
{
    inline static void primes()
    {
        print_below<n - 1>::primes();
        constexpr bool is_n_prime = is_prime(n);
        if(is_n_prime)

            std::cout << ", " << n;
    }
};

int main()
{

    std::cout << "Some primes: \n";
    print_below<8000>::primes();
    std::cout << std::endl;

    // constexpr std::uint64_t large_number = 18446744073709551557ull;
    //
    // The following gets executed in runtime even with -O3.
    // Exceeding constexpr compile-time recursion limit makes is_prime to be evaluated at runtime
    //
    // std::cout << large_number << " is prime" << std::boolalpha << is_prime(large_number) << std::endl;

    // constexpr std::uint64_t large_number = 18446744073709551557ull;
    //
    // The following will not compile, since assigning to a constexpr variable
    // force compile-time evaluation, but is_prime can't be evaluated at compile-time
    // since its evaluation exceeds the constexpr compile-time recursion limit.
    // So assigning to a constexpr variable or using the expressing in constexpr contexts (like array bounds)
    // is the only safe way to assure things are evaluated at compile-time.
    //
    // constexpr bool is_large_number_prime = is_prime(large_number);
    //
    // if(is_large_number_prime)
    //     std::cout << large_number << " is prime" << std::endl;
    // else
    //     std::cout << large_number << " is not prime" << std::endl;

    // This is the largest prime that can be calcutated with is_prime at compile-time on
    // clang version 3.4 (trunk 183073) with the default -fconstexpr-depth=512
    // constexpr std::uint32_t large_number = 262139;

    // This one won't compile anymore, increase with -fconstexpr-depth option.
    constexpr std::uint32_t large_number = 262147;

    constexpr bool is_large_number_prime = is_prime(large_number);
    if(is_large_number_prime)
        std::cout << large_number << " is prime" << std::endl;
    else
        std::cout << large_number << " is not prime" << std::endl;
}

[Murilo Adriano Vasconcelos]

Olá Erle,

existem algumas definições diferentes do que são os números primos (o que em fato dá no mesmo conjunto de números, o que difere é a ideia de como eles são formados) mas essa definição que você postou definitivamente não é correta.

Ah e a respeito de algumas respostas anteriores, 1 não é primo (acho que vi um programa ali que o considera primo).

[]'s

Murilo Adriano Vasconcelos

http://clever-lang.org

[Уθя¡ςκ]

Ah e a respeito de algumas respostas anteriores, 1 não é primo (acho que vi um programa ali que o considera primo).

[]'s

fixed 

[Murilo Adriano Vasconcelos]

Fiz um teste com o programa do  Уθя¡ςκ alterando-o para inserir o primo num std::vector ao invés de imprimí-lo. Achei estranho mas funcionou.

Assim o programa pode ser usado para verificar valores desconhecidos em tempo de compilação, desde que você tenha chamado a meta-função com o maior primo possível verificado pelo seu programa. Um exemplo: http://ideone.com/tNWuDz (note que chamei pra 800 pois o ftemplate-depth do ideone é 900).

Bom, achei estranho e ao mesmo tempo muito legal que podemos usar um vector por exemplo em tempo de compilação. Alguém aí sabe como isso funciona?

2013/6/1 Уθя¡ςκ <obl...@gmail.com>

Ah e a respeito de algumas respostas anteriores, 1 não é primo (acho que vi um programa ali que o considera primo).

[]'s

fixed 

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 
 
 

--
Murilo Adriano Vasconcelos

http://clever-lang.org
http://murilo.wordpress.com

[Уθя¡ςκ]

Nada de mais, é o mesmo princípio do inicial com prints, apesar da lógica curta, a template recursiva vai gerar um código objeto burro que não passa de uma lista de comandos com utilizando os primos pré-calculados. No final, o executável é só uma lista de couts/push_backs somente de primos.

[Уθя¡ςκ]

E o preenchimento/print é em tempo de execução, não de compilação (o vector não é e não tem como ser preenchido assim).

[Murilo Adriano Vasconcelos]

Não entendi, você está dizendo que o cálculo não é feito em tempo de compilação?

[Уθя¡ςκ]

Os primos são pré-calculados em tempo de compilação, porém os push_back's/cout's nunca são executados em tempo de compilação, eles são adicionados ao código objeto, uma bela lista deles no final das contas, com as constantes sendo passadas. Quando o programa é executado, é que o vector cresce, não na compilação.

[Erle Carrara]

Murilo,

Vocês têm razão. Vou ficar com a versão em inglês da Wikipédia, mais confiável!

Obrigado.

[Erle Carrara]

Muito legal isso! (Precisava dizer isso)

[Уθя¡ςκ]

Prá finalizar, este sim vai inicializar um std::array em tempo de compilação ("ao que parece", a lista booleana de is_prime, pelo menos, está visível em segmento a parte no assembly output):

https://gist.github.com/oblitum/5692062#file-compile-time-primes-2-cpp

Mesmo interessante, este tipo de técnica é abuso pro dia-a-dia, e, o compilador não aguenta tanto =/ Neste ultimo sample, não consegui chegar a um array com 2000 elementos sem o compilador dar pau, acredito que por causa do envolvimento com lista de parâmetros template enormes.

No sample anterior que não envolvia variadic templates começa a dar pau por volta dos 10000 na recursão de template. Não estressei a recursão de constexpr isolada pra ver até onde vai sem dar pau.

nota: acho que é seguro dizer, nem tente no msvc.

[P.]

Em sábado, 1 de junho de 2013 19h03min48s UTC-3, Уθя¡ςκ escreveu:

Nada de mais, é o mesmo princípio do inicial com prints, apesar da lógica curta, a template recursiva vai gerar um código objeto burro que não passa de uma lista de comandos com utilizando os primos pré-calculados. No final, o executável é só uma lista de couts/push_backs somente de primos.

Podemos concluir que o seu programa é essencialmente equivalente a um programa com uma tabela de primos hard-coded?

Não parece uma resposta legítima para uma maratona.

--
 P.

[Уθя¡ςκ]

O samples foram criados com a intenção de ilustrar manipulação de primos em tempo de compilação, como Erle havia demonstrado interesse. Se isso vai se encaixar ou não em uma solução de um determinado problema, só vendo, até uma tabela simples pode ser a melhor solução dependendo do caso.

No entanto, exercitar essa forma de programação acarreta em benefícios do tipo, ao se limitar a implementar um função constexpr acabou que levando a um algoritmo recursivo (assumindo como adequado o algoritmo), e que, da forma que foi escrito, ainda ganha em performance por ser tail-recursive, ou seja não perde pra uma implementação em loop equivalente, e ainda serve também pra fazer cálculo em tempo de compilação tanto quanto de execução, ficando a escolha a critério do programador e do problema.

[Maicon]

Para o pessoal que gosta de otimizar o código, segue um dos primeiros desafios do project Euler:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

T+

[Уθя¡ςκ]

Desfinalizando, acho que esse é o basicão final mais enxuto com número de passos  ~raiz(P) / 2 pra um primo P, que é o pior caso de varredura:

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{

    return counter >= limit
        ? number % limit != 0
        : number % counter
            ? is_prime(number, number / counter, counter + 2)

            : false;
}

template<typename T>
constexpr bool is_prime(T n)
{

    return n == 2 || n == 3 || n == 5
        ? true
        : n <= 1 || n % 2 == 0
            ? false
            : is_prime(n, n / 3, T{3});
}

Ele é um algoritmo tail recursive, fiquei interessado em conhecer opções muito melhores que esta mas que também sejam algoritmos tail recursive e que de preferência se encaixam em uma função constexpr. Eu dei uma olhada muito por cima sobre os algoritmos para números primos dos linques anteriores, a maioria se trata de soluções loop clássicas.

Alguém manja?