Mostra os numeros primos e nao primos de 1 a 1000

juninhopaiva · 23 de março de 2012

Queria uma ajuda ai. tenho que fazer um programa em C, no qual ele mostre todos os numeros primos e nao primos de 1 a 1000. eu comecei ai, mas nao ta dando mt certo.

#include <stdio.h>

#include <stdlib.h>

int main(int argc, char *argv[]){

int n;

int num_div;

int div;

num_div = 1;

printf("Veja quais numeros sao primos de 0 a 1000\n\n");

for (n=0; n<=1000; n++){

for (div=0; div<=n; ++div){

if(n%div==0){

num_div++;

}

if(num_div==2){

printf("\n%d é primo\n", n);

}

else{

printf("\n%d nao é primo\n", n);

}

system("PAUSE");

return 0;

}

Nerd Solitário · 23 de março de 2012

Salve Juninho,

Vou te dar a dica. Agora basta você pensar um pouco e colocar um loop no meu codigo!

int main()
{

int cont = 1, cont2 = 0, n1;

printf("Digite um numero: \n");

scanf("%d", &n1);

while (n1 < 0){

printf("Digite um numero maior que 0: \n");

scanf("%d", &n1);

}

while (cont<= n1){

if ((n1 % cont)==0){

cont2++;

}

cont++;

}

if (cont2 == 2){

printf("\nNumero e Primo \n");

}

else{

printf("\nNumero nao e Primo \n");

}

return 0;

}

Listeiro 037 · 23 de março de 2012

Ainda está pesado.

Dá pra fazer testando a divisão só por números ímpares e pulando os testes de 2 em 2.

E dividindo somente até 31.

O que for par mostra-se mensagem igual ao que não for primo, exceto para 2.

23 de março de 2012

divide ate menos que a metade do numero.

ja vi uns algoritmos que usavam raiz quadrada

Listeiro 037 · 23 de março de 2012

divide ate menos que a metade do numero.
ja vi uns algoritmos que usavam raiz quadrada

Exatamente.

31 x 31 < 1000 < 32 x 32

961 < 1000 < 1024

Matheus Maldi · 24 de março de 2012

fiz um algoritmo que mostra todos até 10000 instantaneamente

a ideia é dividir apenas pelos numeros primos ja encontrados, que ficaram guardados numa lista, o 2 é adicionado no começo, e ele só busca por numeros impares.

#include <stdio.h>
#include <stdlib.h>

struct Lista
{
	int source[10000];
	int size;
};

typedef Lista lista;

lista* newlista()
{
	lista * result = (lista*)malloc(sizeof(lista));	
	result->size = 0;
	return result;
}

void listaadd(lista *l, int i)
{
	l->source[l->size] = i;
	l->size++;
}

int main()
{
	lista * lprimo = newlista();

	listaadd(lprimo, 2);

	for (int i = 3; i < 10000; i += 2)
	{
		for (int j = 0; j < lprimo->size; j++)
		{
			if (i % lprimo->source[j] == 0) goto pulaadd;
		}
		listaadd(lprimo, i);

		pulaadd:;
	}

	for (int i = 0; i < lprimo->size; i++)
	{
		printf("%d\t", lprimo->source[i]);
	}

	getchar();
	return 0;
}

Dani0liveira · 24 de março de 2012

só uma duvida,

int source[10000];

Vamos ver, um int normalmente tem uns 2 bytes, você usou 20000 bytes para armazenar esse vetor só para um programinha pequeno? imagine em um grande projeto.

Listeiro 037 · 25 de março de 2012

fiz um algoritmo que mostra todos até 10000 instantaneamente

a ideia é dividir apenas pelos numeros primos ja encontrados, que ficaram guardados numa lista, o 2 é adicionado no começo, e ele só busca por numeros impares.

#include <stdio.h>
#include <stdlib.h>

struct Lista
{
	int source[10000];
	int size;
};

typedef Lista lista;

lista* newlista()
{
	lista * result = (lista*)malloc(sizeof(lista));	
	result->size = 0;
	return result;
}

void listaadd(lista *l, int i)
{
	l->source[l->size] = i;
	l->size++;
}

int main()
{
	lista * lprimo = newlista();

	listaadd(lprimo, 2);

	for (int i = 3; i < 10000; i += 2)
	{
		for (int j = 0; j < lprimo->size; j++)
		{
			if (i % lprimo->source[j] == 0) goto pulaadd;
		}
		listaadd(lprimo, i);

		pulaadd:;
	}

	for (int i = 0; i < lprimo->size; i++)
	{
		printf("%d\t", lprimo->source[i]);
	}

	getchar();
	return 0;
}

só uma duvida,
int source[10000];

Vamos ver, um int normalmente tem uns 2 bytes, você usou 20000 bytes para armazenar esse vetor só para um programinha pequeno? imagine em um grande projeto.

É um nodo com 10000 elementos ou era prá ser uma lista com 10000 nodos?

Matheus Maldi · 27 de março de 2012

só uma duvida,
int source[10000];

Vamos ver, um int normalmente tem uns 2 bytes, você usou 20000 bytes para armazenar esse vetor só para um programinha pequeno? imagine em um grande projeto.

Olhe, com a com 100000 elementos o programa usou 672k(sendo 391k a lista) de memoria sendo , hoje em dia é normal um pc ter mais de 1GB de ram livre

1GB -> 1024MB -> 1048576k, com 1GB de ram poderiamos criar 2691 listas desta.

lembrando que você também pode destruir a lista após usando o metodo free();

27 de março de 2012

Matheus, não se baseie nesse único arquivo.

Em grandes projetos 'reais' ele seria apenas uma minúscula parte.

Ideias criativas sao sempre validas, como a sua, mas essa é um pouco inviável, pois 100000 é um número bem pequeno.

Vai aumentando o numero, pra 1 milhao, 10 milhoes,...,1 bilhao...que seu arquivo ja que atinge uns Gb. Ele só é rápido nesses casos mais simples.

E você confundiu a memória ram com a do HD.

E não se baseie no tamanho absoluto do arquivo, e sim do relativo.

Pra um código simples, o tamanho desse é absurdamente grande.

Listeiro 037 · 27 de março de 2012

int aguenta inteiros sem sinal de quantos bytes?

Para 2, vai até 2^16. Para 4, vai até 2^32. Para 8, 2^64.

Matheus Maldi · 27 de março de 2012

Ola, em projetos grandes, com certeza eu usaria o free() para limpar a memoria, não existe problema nenhum em criar um array deste tamanho, você tem que saber o que esta fazendo.

um array de 100000 int é pequeno (ocupa menos de 400k na memoria), vocês se importam que um programa pequeno use 400k a mais na memoria e esquecem da performance

Sobre o tamanho do int, basta usar sizeof(int), este é o numero em bytes

Listeiro 037 · 27 de março de 2012

Esse aqui é beeem OFF. Porém como eu ainda não reparei em semelhante por aqui:

Isso aqui é um algoritmo-base feito em uma outra linguagem.

É um crivo simples que lista apenas primos de 1 a 10000.

Usa listas.

Se a lista for implementada semelhantemente ao daqui, fica fácil fazer em C.

Eu consegui melhorar comparado à última vez que fiz.

Se tiver a permissão de deixar aqui .

Serve de comparação, até prá entender o que pode ser melhorado se feito em C.

Não tem coisas obscuras e o mínimo pode ser explicado, até porque a estrutura é lista.

#!/usr/bin/perl

use strict;
use warnings;

my @primes=(2, 3);

my ($i, $j, $k) = (5, 0, 0);

do {

	$j = 0;
	$k=sqrt($i);

	do {} while ($primes[++$j]<$k and ($i%$primes[$j]));

	push (@primes, $i) if ($primes[$j]>$k);

	$i+=(($i%3==2)?2:4);

} while ($i<=10000);

foreach (@primes) {
	print "$_ ";
}

print "\n";

*** ADD ***

Aqui uma versão em C:

#include <stdio.h>
#include <math.h>

typedef unsigned long long llint;


int main (void) {

	const llint p = (llint) (pow (2.0, 23.0) -1.0);
	const llint q = 1009999; // (llint) (2.0 * ((double) p / log((double) p)));

	llint primes[q];

	llint i=5, j=0, k=0, l=1, m=0;

	for (m=0; m<q; m++) primes[m]=1;

	primes[0]=2;
	primes[1]=3;

	do {

		j = 0;
		k= (llint) sqrt((double) i);

		while ((primes[++j]<k) && (i%primes[j]));

		if (primes[j]>k) primes[++l] = i;

		i+=((i%3==2)?2:4);

	} while (i<p && l<q);

	for (m=0; m<l; m++) printf ("%llu ",primes[m]);
	putc ('\n',stdout);

	return 0;

}