Red de conocimiento informático - Conocimiento de la instalación - Buscando el código para determinar números primos en lenguaje C!!!!!

Buscando el código para determinar números primos en lenguaje C!!!!!

Idea básica: utilizar m como dividendo y 2-INT ( ) como divisor. Si ambos no se pueden dividir, m es un número primo; de lo contrario, no lo es.

El siguiente segmento de programa se puede utilizar para implementar:

void main()

{ int m,i,k;

printf("ingrese un número:\n");

scanf("%d",&m);

k=sqrt(m);

for(i =2;i

si(m%i==0) romper;

if(i>=k)

printf("El número es un número primo");

else

printf("El número no es un número primo");

}

Cámbielo Escrito como una función, devuelve 1 si es un número primo, de lo contrario devuelve 0

int prime( m%)

{int i,k;

k=sqrt (m);

for(i=2;i

if(m%i= =0) devuelve 0;

devuelve 1;

}

Información ampliada:

Encontrar números primos mediante el método del tamiz

1. Ideas básicas

Uso La idea básica de encontrar números primos mediante el método del tamiz es:

Organizar los números enteros positivos comenzando desde 1 y dentro de un rango determinado. de pequeño a grande. Si 1 no es un número primo, búsquelo primero. Elija el número primo más pequeño de los números restantes y luego elimine sus múltiplos. Y así sucesivamente, hasta que el colador esté vacío.

Si corresponde:

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1 no es un número primo, así que elimínelo. Entre los números restantes, 2 es el más pequeño y es un número primo. Si se eliminan los múltiplos de 2, los números restantes son:

3 5 7 9 11 13 15 17 19 21 23 25 27 29<. /p>

El resto Entre los números a continuación, 3 es el más pequeño y es un número primo. Elimina los múltiplos de 3 y continúa hasta que todos los números hayan sido tamizados. El número primo encontrado es:

2 3 5 7 11 13 17 19 23 29

2. Implementación de C++

1: Sea A un número primo, luego A*N (N>1; N es un número natural) no son números primos.

#define?range?2000

bool?

IsPrime[range+1];

/*set determina si es un número primo y el resultado se almacena en IsPrime[i]. ¿Esta función se prueba en DEV?

C++*/

void?set(bool?IsPrime[])

{

int?i,j;

for(i=0;i<=rango;++i)

IsPrime[i ]=true;

IsPrime[0]=IsPrime[1]=false;

for(i=2;i<=range;++i)

{

if(

IsPrime[i])

{

for(j=2*i; j<= range;j+=i)IsPrime[j]=false;}}}

2.

Explicación: El truco para resolver este problema es cómo organizar el orden de eliminación de modo que cada número que no sea primo se elimine solo una vez. Aprendí un teorema de factorización en la escuela secundaria. Dijo que cualquier número no primo (compuesto) se puede descomponer en productos consecutivos de números primos.

Por ejemplo, 16=2^4, 18=2 * 3^2, 691488=2^5 * 3^2 * 7^4, etc. Si el número primo más pequeño en factorización se escribe en el extremo izquierdo, 16=2^4, 18=2*9, 691488=2^5 * 21609,;

En otras palabras, el número compuesto N Escrito como N = p ^ k * q, en este momento q es, por supuesto, mayor que p, porque p es el número primo más pequeño en factorización. Debido a la unicidad de la factorización, la forma en que cualquier número compuesto N se escribe como N=p^k * q también es única.

Debido a la relación de q>=p, al eliminar números no primos, si se sabe que p es un número primo, puede eliminar p^2, p^3, p^4. .. primero, y luego elimine pq, p^2*q, p^3*q,..., (q es un número mayor que p pero no se elimina), hasta pq>N.

Debido a que cada número no primo se elimina solo una vez, se puede imaginar que la velocidad de este programa debe ser bastante rápida. Según el artículo de Gries y Misra, el tiempo lineal, es decir, el tiempo proporcional a N, es suficiente (en este caso necesitamos encontrar el número primo de 2N). ?

El código es el siguiente:

#include

#include

using?namespace?std ;

p>

int?main()

{

int?N;?cin>>N;

int?* Ubicación=nuevo?int [N+1];

for(int?i=0;i!=N+1;++i)

Ubicación[i]=i ;

Ubicación[1]=0;?//Parte del filtro?

int?p,q,end;

end=sqrt((double) N)+1 ;

for(p=2;p!=end;++p)

{

if(Ubicación[p])

{

for(q=p;p*q<=N;++q)

{

for(int? k=p* q;k<=N;k*=p)

Ubicación[k]=0;

}

}

}

int?m=0;

for(int?i=1;i!=N+1;++i)

{

if(Ubicación[i]!=0)

{

cout<

+ +m;

}

if(m%10==0)?cout<

}

cout<

return?0;

}

Este código pasó la prueba en el entorno Visual Studio 2010 .

La velocidad de los dos algoritmos anteriores es casi la misma en datos pequeños.

Referencia: Enciclopedia Baidu-Encontrar números primos mediante el método del tamiz