Es primo o no

Estado
Cerrado para nuevas respuestas.
T

Tavo

[color=#BF0000]Lucha por tus ideales![/color]
Ty algoritmo tiene una complejidad de O(n), cuando podría ser menor (Y ademas de que tu algoritmo siempre va a calcular todos los números).
La mejor forma de hacer esto (Sin Programación Dinámica), es hacerse una dividir a los números por números primos.
En caso de que solo se fije una vez si es primo, lo que le agregaría a tu algoritmo es un chequee de si es divisible por 2 para acelerar el proceso, pero si se va a buscar varias veces lo mejor es crear una HashTable con los números primos comprendidos entre 0 - N, y despues dividir por ellos.
 
P

Pocho

Oráculo Lvl 3
si, esto nada mas lo hise para mostrar la funcion MOD, pero si, ahora lo estoy desarrollando enserio, no entendi lo de la hash table
 
T

Tavo

[color=#BF0000]Lucha por tus ideales![/color]
Yo tengo bocha de este tipo de algoritmos hechos en C++ para competencias, etc...
 
P

Pocho

Oráculo Lvl 3
If Num Mod 2 = 0 Or Num < 2 Then Exit Function

eso no esta bien ahi, va, en realidad si, pero si vamos a buscar primos entre un rango de numeros (1 a 1000) combiene en el bucle, ponerle q vaya sumando de a 2,como el tuyo ^^

pd: el 1 no es primo?
 
T

Tavo

[color=#BF0000]Lucha por tus ideales![/color]
No. Un número es primo cuando es divisible solo por dos números. Él 1 es solo divisible por 1, al igual que el 0, pero eso se contrapone a lo que muchos dicen que "Un número es primo cuando es divisible por si mismo y 1".

Peleas matemáticas, pero a mi me lo enseñaron como que él 1 no es primo.
 
P

Pocho

Oráculo Lvl 3
Los no licenciados en ciencias exactas, se pueden preguntar el porqué el número uno no es primo a pesar de cumplir con los requisitos de la definición de número primo: el uno solo es divisible por sí mismo (uno) y por la unidad (uno). La respuesta a esta cuestión es la siguiente: el número uno no se considera número primo por convenio internacional entre matemáticos.
Haz clic para expandir...

Fuente: <a href="http://209.85.165.104/search?q=cache:Mb" class="postlink" rel="nofollow" onClick="window.open(this.href);return false;">http://209.85.165.104/search?q=cache:Mb</a> ... cd=1&gl=ar



nose, si, peleas

a)"Todo número par mayor que dos es suma de dos números primos"


entonces el 1 es primo, se contradicen

a) "Todo número impar mayor que 5 es suma de un número primo y el doble de otro primo"

el numero 3 x 2 = 6 + 1 (en este caso primo) = 7


es decir, el 1 es primo
 
P

Pocho

Oráculo Lvl 3
en realidad es discutir por algo sin sentido, casi, podrias poner algun codigo de numeros primos en C++ o C asi lo veo ? xd
 
Z

Zy

Newbie Lvl 2
En un foro que frecuento hicieron algo parecido. Esta hecho en java y te muestra una lista de los numeros primos del 1 al 20000. Hay varias funciones para verificar si es primo. Fijate aca.

<a href="http://foros.hackerss.com/index.php?showtopic=2577&st=0" class="postlink" rel="nofollow" onClick="window.open(this.href);return false;">http://foros.hackerss.com/index.php?showtopic=2577&st=0</a>

PD: Si queres hacer una lista no te conviene crear una funcion que verifique si es primo o no. Te conviene crear una lista de numeros no primos. Fijate el ultimo post que esta mi programa. Hasta ahora el mas rapido jaja. Te hace la lista hasta el 20000 en 2 milisegundos :)
 
P

Pocho

Oráculo Lvl 3
no podemos dejar de ver esto :S


ROGRAMADOR: 1 es primo, 1 es primo, 1 es primo, 1 es primo, ...

FÍSICO CUÁNTICO: Todos los números son igualmente primos y no primos hasta que son observados.

VENDEDOR DE SOFTWARE: 1 es primo, 2 es primo, 3 es primo, 4 es primo, 5 es primo, 6 es primo, 7 es primo, 8 es primo,... ¡Más primos que nadie en el mercado, por el mismo precio!

CATEDRÁTICO: 3 es primo, 5 es primo, 7 es primo, los demás son ejercicios para los estudiantes.

PROGRAMADOR: 3 es primo, 5 es primo, 7 es primo, 9 dejará de ser primo en la próxima versión.

PROGRAMADOR DE BASIC: ¿Qué es un número impar?

PROGRAMDOR DE COBOL: ¿Qué es un número primo?

PROGRAMADOR DE WINDOWS: 1 es primo, ha ocurrido un error, apriete cualquier tecla para volver a empezar.
Haz clic para expandir...


qiebra el hielo :D



es logico q c++ va a tardar poco xD


ami en vb me tarda 5 segundos aprox.



pero es mejor c++ desde ya, asik voy a afanarte el codigo :D
 
Z

Zy

Newbie Lvl 2
Mira. No importa tanto que este en C++, sino que me di cuenta de poner ese break, eso aceleró todo unas 100 veces :|

Tampoco te niego que vb es lento jaja

Y si me robas el cdigo pone una referencia :p
<a href="mailto:[email protected]" class="postlink" rel="nofollow" onClick="window.open(this.href);return false;">[email protected]</a> :)
 
P

Pocho

Oráculo Lvl 3
la pongo aca :p


#include

bool primos[20001];

void FillList(){

int i;
int m;

for(i=2;i 20000) break;
primos[m*i] = true;
}
}
}

int main()
{
system("PAUSE");
std::cout << "Empieza\n";
for(int i = 1;i<=1000;i++) // AQUI LLENAMOS LA LISTA 1000 VECES. BORREN ESTA LINEA PARA HACERLO UNA VEZ
FillList();
std::cout << "Lista llena\n";
std::cout << "Presione una tecla para imprimir.";
system("PAUSE");

for(int i = 1;i<=20000;i++){
if(primos != true){
std::cout << "Es primo: " << i << std::endl;
}
}

system("PAUSE");
}
Haz clic para expandir...


para q sirve el break ese xd
 
Z

Zy

Newbie Lvl 2
Sería un exit for. Asi no sigue probando numeros al pedo.

Con este break para en el 20000 en vez del 100.000.000 xD

Ves porque la rapidez :p
 
T

Tavo

[color=#BF0000]Lucha por tus ideales![/color]
Cargar un vector es realmente facil, mas si se usa el std::vector, logras una performance mayor.
 
P

Pocho

Oráculo Lvl 3
Tavo dijo:
Cargar un vector es realmente facil, mas si se usa el std::vector, logras una performance mayor.
Haz clic para expandir...
q qiere decir?


pàra al otro , si, es c++


q merda es std::vector

a ver , pone vos un codigo c++ a ver q tan veloz :p
 
Estado
Cerrado para nuevas respuestas.
Arriba