¿Cómo podemos decir que un número es primo usando su raíz cuadrada?

Answer 1

Como antes, si decimos 203, verifíquelo como candidato para prime.

Listar todos los números primos debajo de 203

lista (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, 97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199), los siguientes 211.

Si el número 203 no es primo, entonces existe una descomposición primaria p1 * p2 * p3 * .. = El número es todo p1, p2, .. uno de la lista anterior. Ahora reagrupamos la descomposición primaria para que p1 sea el más pequeño y pi <= pj cuando i <= j. Ahora empiezas a buscar primos de i = 1 de nuestra lista, verificando si el resto es cero después de dividir a nuestro candidato:

divide 203 por 2 y el resto es 1 pero el cociente es 101, es el más cercano en la lista

203 = 2 * 101 + 1 101 primo más cercano al cociente.

divide 203 por 3 y el resto es 2 y el cociente es 67 pero 67 es primo

203 = 3 * 67 +2 67 primo más cercano

203 = 5 * 40 + 3 41 más cercano

203 = 7 * 29 el resto cero significa que el candidato no fue primo y su descomposición primaria es 7 * 29. Usted ve cómo a medida que la secuencia de obtención obtiene primos más altos, la secuencia de primos más cercana obtiene primos más bajos, porque estamos dividiendo por números más grandes.

2 * 101

3 * 67

5 * 41

Bingo 7 * 29

Cuando una secuencia sube, la otra baja. Se cruzarán en pi = pj = P ^ 2 que es sqrt (203) = 14,2479 … si paso esta línea recuperando números primos y no encontré un resto cero, no tiene sentido seguir buscando porque la secuencia “abajo” ya los ha revisado.

Aquí tienes una lista de primos de hasta cien mil, que hice con un java sw propio. Creo que no contiene errores, pero este párrafo es un descargo de responsabilidad, por si acaso.

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,443,449,457,461,463,467,479,487,499,509,521,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,643,653,661,683,691,701,709,719,727,733,739,743,757,761,773,787,797,811,821,823,827,829,839,853,857,859,863,877,883,887,911,919,929,937,947,953,967,971,983,991,997, 1009,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1073,1087,1097,1103,1109,1117,1123,1129,1153,1163,1171,1181,1187,1193, 1201,1213,1217,1223,1231,1237,1249,1259,1277,1279,1289,1291,1301,1303,1307,1327,1357,1361,1381,1409,1423,1433,1439,1447,1451, 1459,1471,1481,1483,1493,1499,1543,1549,1553,1559,1567,1571,1579,1583,1609,1613,1619,1627,1637,1657,1667,1669,1697,1699,1709, 1723,1733,1741,1747,1753,1789,1801,1811,1831,1847,1861 , 1867,1871,1873,1877,1901,1907,1913,1931,1933,1943,1949,1951,1987,1993,1997,2003,2017,2027,2047,2053,2063,2069,2083,2099,2111 , 2113,2131,2141,2143,2153,2161,2179,2221,2237,2267,2269,2273,2281,2357,2371,2381,2383,2389,2393,2399,2411,2437,2441,2447,2473 , 2477,2503,2539,2549,2551,2557,2579,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2693,2741,2753,2767,2789,2791 , 2797,2801,2837,2843,2851,2861,2887,2897,2909,2917,2927,2939,2957,2963,2999,3011,3049,3067,3083,3109,3119,3121,3163,3191,3209 , 3251,3257,3271,3299,3301,3307,3319,3329,3343,3361,3371,3449,3457,3463,3467,3469,3499,3517,3527,3539,3541,3547,3557,3559,3581 , 3583,3593,3613,3617,3623,3643,3671,3691,3701,3769,3779,3793,3797,3803,3847,3863,3881,3917,3919,3923,3929,4013,4021,4049,4057 , 4093,4139,4159,4177,4217,4231,4241,4271,4337,4363,4373,4421,4441,4447,4451,4457,4481,4507,4517,4523,4591,4603,4637,4649,4657 4679,4721,4723,4733,4751,4759,4787,4789,4799,4801,4813,4831,4843,4891,4903,4933,4943,4957,4967,4973,4987,4993,4999,5003,5009 , 5021,5023,5077,5087,5107,5119,5167,5171,5227,5293,5381,5387,5407,5413,5417,5419,5437,5441,5503,5521,5531,5563,5573,5689,5741 5779,5783,5813,5857,5867,5897,5981,6011,6043,6047,6053,6091,6101,6121,6131,6133,6143,6163,6173,6187,6203,6229,6257,6277,6287 6299,6337,6373,6389,6397,6473,6491,6551,6571,6581,6637,6691,6701,6719,6733,6763,6779,6803,6823,6833,6863,6869,6871,6967,6971 , 6977,6997,7001,7027,7159,7181,7193,7207,7213,7283,7321,7331,7351,7411,7451,7453,7481,7489,7499,7507,7517,7547,7561,7573,7639 , 7649,7699,7717,7741,7793,7823,7829,7853,7877,7883,8011,8069,8089,8191,8209,8219,8233,8243,8263,8273,8293,8311,8369,8389,8431 , 8471,8521,8537,8543,8563,8573,8627,8647,8677,8699,8719,8741,8761,8849,8867,8887,8929,8933,8963,9013,9041,9043,9133,9137,9157 , 9161,9181,9221,9241,9257,9277,9319,9377,9397,9433,9439,9467,9511,9521,9661,9689,9697,9743,9773,9803,9811,9839,9901,9923,9941 , 9967,10069,10079,10091,10099,10133,10151,10163,10169,10181,10243,10253,10273,10321,10327,10357,10369,10391,10427,10471,10513 , 10607,10627,10667,10687,10691,10711,10733,10739,10753,10831,10859,10901,10921,10967,10993,11003,11057,11113,11131,11173,11197,11279,11293,11311,11321 , 11351,11371,11377,11477,11527,11657,11731,11789,11863,11933,11953,11993,12073,12143,12163,12197,12227,12239,12269,12289,12307,12487,12491,12497,12511 , 12517,12527,12541,12547,12641,12671,12697,12703,12827,12893,12953,12959,13001,13147,13159,13163,13183,13187,13333,13367,13397,13487,13501,13537,13591 , 13597,13649,13799,13829,13841,13883,13913,13963,13967,13973,13997,14011,14029,14039,14123,14153,14173,14207,14213,14293,14303,14317,14323,14327,14351 , 14381,14407,14419,14437,14447,14461,14591,14627,14633,14639,14657,14681,14753,14821,14831,14851,14933,14957,14969,14983,15217,15227,15233,15241,15263 , 15329,15347,15349,15359,15377,15401,15413,15451,15461,15469,15553,15611,15679,15683,15739,15749,15787,15817,15991,16061,16111,16229,16267,16283,16333 , 16361,16369,16487,16649,16759,16843,17021,17041,17047,17077,17263,17293,17389,17401,17419,17497,175 39,17581,17621,17687,17711,17713,17737,17747,17863,17911,17921,17981,17989,18059,18079,18181,18287,18329,18379,18451,18461,18637,18643,18701,18721, 18731,18913,18973,19051,19141,19211,19231,19241,19273,19309,19319,19391,19463,19483,19493,19633,19637,19793,19891,19993,20023,20117,20161,20201,20297, 20327,20347,20357,20389,20399,20479,20509,20771,20819,20821,20857,20921,20941,21013,21023,21121,21247,21397,21407,21481,21491,21521,21569,21589,21599, 21737,21757,21767,21799,21851,21871,21881,21901,21991,22037,22277,22279,22343,22349,22453,22483,22501,22511,22531,22571,22751,22921,22927,23087,23099, 23117,23143,23173,23293,23333,23459,23521,23531,23537,23557,23633,23669,23689,23719,23747,23753,23767,23857,23879,23899,23909,23941,24071,24113,24197, 24221,24373,24443,24499,24509,24587,24617,24811,24823,24919,24943,24953,25097,25117,25127,25147,25171,25339,25349,25393,25463,25469,25621,25679,25703, 25723,25759,25763,25981,25999,26053,26063,26251,26261,26269,26297,26407,26417,26449,26459,26489,26563,2 6701,26711,26731,26759,26833,26863,27043,27067,27089,27173,27271,27281,27359,27397,27407,27437,27457,27481,27751,27793,27799,27803,27809,27823,27847, 28081,28309,28319,28387,28429,28439,28493,28513,28573,28627,28657,28661,28703,28877,28943,29297,29327,29413,29483,29501,29521,29531,29537,29567,29587, 29723,29753,29833,29881,29903,29921,29929,29947,30089,30119,30161,30187,30271,30293,30403,30427,30467,30529,30539,30757,30791,30881,30887,30971,31159, 31307,31397,31517,31583,31613,31771,32033,32051,32531,32551,32563,32573,32579,32603,32621,32707,32717,32917,32951,32987,32989,33023,33181,33191,33211, 33403,33413,33433,33487,33557,33629,33757,33889,33899,34061,34159,34231,34253,34351,34361,34457,34477,34519,34537,34667,34687,34819,34877,34897,34981, 35041,35083,35099,35111,35221,35311,35527,35537,35543,35573,35869,35879,35899,35923,35933,35963,35977,35983,35993,36013,36131,36151,36161,36181,36403, 36677,36691,36697,36847,36857,36877,36887,36931,36979,36989,37039,37049,37267,37507,37517,37537,37547 , 37591,37643,37663,37673,37879,37889,37951,37963,37993,38113,38123,38149,38281,38327,38629,38639,38651,38653,38671,38681,38699,38737,38747,38767,39023 , 39043,39199,39449,39623,39643,39769,39779,39799,39847,39857,39989,40133,40213,40253,40357,40577,40639,40739,41141,41203,41213,41641,41651,41659,41669 , 41681,41843,41863,41893,41903,41911,42013,42017,42023,42043,42073,42083,42223,42319,42391,42487,42719,42727,42737,42751,42787,42841,42953,42979,42989 , 43013,43081,43271,43291,43361,43447,43487,43499,43721,43733,43963,43973,44087,44119,44129,44411,44599,44657,44729,44741,44771,44893,44959,45053,45161 , 45181,45191,45259,45329,45413,45439,45953,46027,46093,46153,46469,46489,46499,46547,46549,46559,46567,46663,46703,46723,46763,46811,46831,47149,47363 , 47521,47587,47599,47737,47743,47777,47797,47807,47881,47917,47947,48271,48281,48497,48679,48767,48787,49057,49177,49261,49307,49327,49529,49549,49559 , 49639,49663,49669,49957,50053,50077,50123,50249,50261,50291,50371,50543,50647,50971,50989,51041,512 39,51307,51421,51431,51539,51929,51991,52021,52177,52187,52201,52543,52553,52747,52757,52783,52817,53017,53089,53101,53147,53279,53353,53359,53441, 53551,53611,53653,53663,53759,53927,53953,54059,54121,54139,54217,54361,54421,54623,54751,54829,54871,54881,55127,55147,55163,55177,55373,55487,55609, 55619,55639,55747,55859,55901,55921,55931,56113,56123,56179,56197,56249,56257,56281,56453,56461,56477,56519,56527,56983,56993,57059,57151,57373,57389, 57517,57527,57557,57829,57887,58013,58043,58229,58313,58693,58781,58937,59167,59417,59513,59557,59567,59659,59879,59987,60041,60223,60353,60383,60413, 60637,60887,61001,61051,61091,61291,61463,61483,61507,61631,61651,61657,61673,61837,61847,61927,61961,62171,62219,62239,62603,62633,62659,62773,62827, 62851,62969,62989,63103,63113,63127,63493,63577,63719,63841,63851,63977,63997,64007,64231,64333,64403,64433,64453,64483,64513,64523,64693,64747,64783, 64793,65587,65609,65629,65809,65861,66229,66373,66383,66413,66529,66559,66613,66761,66931,67819,67829,6 7867,68207,68227,68371,68399,68477,68531,68743,68881,69263,69283,69371,69431,69497,69557,69593,69613,69827,69857,69877,70111,70121,70123,70207,70237, 70391,70423,70501,70549,70727,70853,70867,70877,70913,70957,71047,71129,71221,71501,71647,71761,71803,71917,71947,72173,72311,72421,72431,72517,72563, 72617,72619,72623,72647,72817,72869,73207,73231,73237,73427,73453,73607,73709,73907,74381,74383,74413,74551,74561,74597,74779,74797,74923,75109,75169, 75181,75211,75277,75743,75773,75793,76163,76273,76283,76369,76427,76529,76883,77041,77263,77279,77551,77611,77621,77641,77813,77929,78137,78157,78229, 78259,78263,78509,78929,79201,79229,79231,79241,79333,79397,79609,79619,79633,80039,80107,80117,80281,80491,80603,80737,80761,80923,80933,80953,80963, 81031,81349,81353,81359,81409,81439,81469,81677,81737,81847,81937,81959,82601,82657,82757,82847,82903,82913,83077,83267,83339,83903,84067,84127,84137, 84157,84391,84401,84463,84509,84533,84551,84811,85061,85067,85081,85091,85441,85781,85817,86027,86209 86297,86363,86381,86413,86423,86491,86531,86539,86561,86687,86689,86729,86747,86759,87127,87161,87317,87323,87491,87511,87539,87541,87623,87691,87701 , 87823,87833,87943,88199,88211,88241,88379,88741,88771,88801,88811,88883,88889,89137,89363,89381,89447,89477,89479,89489,90053,90073,90379,90463,90473 , 90947,90977,91033,91159,91199,91229,91457,91691,91807,92111,92311,92387,92467,92507,92581,92623,92753,92767,92801,92821,92941,92951,93097,93127,93179 , 93199,93887,93901,93911,94483,94543,94559,94613,95203,95233,95327,95419,95429,95477,95483,95747,95959,96001,96241,96253,96281,96451,96517,96989,96997 , 97007,97021,97481,97607,97829,97849,97859,97987,98317,98327,98347,98377,98387,98419,98429,98479,98489,98491,98647,98677,98947,99083,99119,99173,99377 99397,99487,99497,99571,99581,99721,99961,99971,100297,

Answer 2

Ya hay algunas respuestas aquí, pero no son matemáticamente rigurosas, por lo que agregaré una (con suerte) prueba más rigurosa.

Primero necesitamos

Lema: si n es un número entero y existe [matemática] \ text {d} \ ge \ sqrt {n} [/ matemática] de modo que d divide n, entonces existe [matemática] \ text {s} \ le \ sqrt {n} [/ math] tal que s divide n.

Prueba: Elija [math] s = \ frac {n} {d}. [/ Math] Esto divide claramente ny es un número entero porque d divide n, por lo que solo debemos mostrar que [math] \ text {s} \ le \ sqrt {n} [/ math]. Esto se desprende del hecho de que

[matemáticas] \ sqrt {n} \ le d \ Rightarrow \ frac {1} {d} \ le \ frac {1} {\ sqrt {n}} \ Rightarrow \ frac {n} {d} \ le \ frac { n} {\ sqrt {n}} \ Rightarrow s \ le \ sqrt {n} [/ math]

QED

Ahora podemos justificar su algoritmo:

Teorema: un entero n es primo si no tiene divisores [math] s \ le [/ math] [math] \ sqrt {n} [/ math] yn no es un cuadrado perfecto.

Prueba: no hay divisores menores o iguales que [math] \ sqrt {n} [/ math], por lo que todos los factores posibles deben ser mayores o iguales que [math] \ sqrt {n}. [/ Math] Suponga que existe es un divisor [math] d [/ math] [math] \ ge [/mathfont>[mathicsoft\sqrt{n}.[/mathfont>Entonces como consecuencia directa del lema, hay un divisor [math] s \ le \ sqrt {n} [/ math], una contradicción.

QED

Finalmente, como ejemplo, considere 23. Mostraremos que es primo. El teorema dice que solo debemos verificar números enteros menores que 5. Es fácil verificar que 2, 3 y 4 no dividen 23. Por lo tanto, el teorema 23 es primo.

Espero que eso ayude a aclarar esto.

Answer 3

Supongamos que se le pide que encuentre factores de 40.

Si no tiene una mente entrenada, entonces hará algo como esto:

1, 2, 4, 5, 8, 10, 20, 40.

Pero la misma tarea será realizada por una mente entrenada como esta:

1 x 40

2 x 20

4 x 10

5 x 8

Ahora, si observa con atención, encontrará un patrón que mis números del lado izquierdo (es decir, 1, 2, 4, 5) son más pequeños en comparación con el lado derecho (es decir, 40, 20, 10, 8). Y usando solo un factor (ya sea el lado izquierdo o el lado derecho) puedo encontrar otro factor.

Otra observación importante es que todos los números del lado izquierdo son menores que la raíz cuadrada de 40 y los números del lado derecho son mayores que la raíz cuadrada de 40.

Entonces, si divido 40 con el valor menor que la raíz cuadrada de 40, que está entre 6 y 7.

Si piensas ¿Cómo lo encontré?

También es simple, el cuadrado de 6 es 36 y el cuadrado de 7 es 49. Mi número es 40 para el cual quiero verificar la condición principal. Eso simplemente significa que la raíz cuadrada de 40 debe ser mayor que 6 (porque el cuadrado de 6 es 36) y menor que 7 (porque el cuadrado de 7 es 49).

Entonces dividiré 40 con todos los números del 2 al 5 y si alguno de los números puede dividirlo, eso simplemente significa que el número no es primo.

Ahora suponga que desea verificar si 181 es primo o no.

1. Encuentre la raíz cuadrada de 181 que es 13 .____ (es decir, 13 x 13 = 169 y 14 x 14 = 196)
2. Divide 181 con todos los números <= 13.
3. No es divisible, eso significa que es un número primo.

Answer 4

Ok, digamos que estás tratando de averiguar si [math] 101 [/ math] es primo. Tienes [matemáticas] 10 <\ sqrt {101} <11 [/ matemáticas].

Si [math] 101 [/ math] fuera un múltiplo de [math] 11 [/ math], tendría [math] 101 = 11k [/ math] para algún número entero [math] k [/ math]. Pero ese número entero [math] k [/ math] tendría que ser menor que [math] 11 [/ math], ya que [math] 11 ^ 2> 101 [/ math]. Esto significa que si ha marcado todos los naturales [matemática] n [/ matemática] con [matemática] n <\ sqrt {101} [/ matemática], y ninguno de ellos dividió [matemática] 101 [/ matemática], ya sabe [matemáticas] 11 [/ matemáticas] no puede dividir [matemáticas] 101 [/ matemáticas].

Y en lugar de verificar todos los naturales, puede verificar todos los números primos (vea la imagen GIF en la parte superior derecha de esta página: Tamiz de Eratóstenes)

Answer 5

Digamos que 257 es su número en el cálculo.

Ahora la raíz cuadrada será 16.xx

El proceso

• Tome el entero más grande [función de caja] de 16.xx, que es 16.
• Considere solo números primos hasta el 16 para verificar si dichos números son factores de 257.
• Tomando 2, 3, 5, 7, 11 y 13, uno encontraría que 257 no es divisible por ninguno de estos, lo que convierte a 257 en un número primo.

Digamos 169 es el número.

La raíz cuadrada es 13 (ya es un número entero), por lo que al verificar números primos hasta 13 se obtiene que 169 es divisible por 13, por lo que 169 no es un número primo.

Editado: ¡ Muchas gracias, David! Mea culpa maxima.

Answer 6

Si N es el número que se está considerando, encuentre la raíz cuadrada de un número o dos más cercanos a sqrt (N). Luego verifique estos (estos) números para ver si (ellos) son factores. Luego verifique los enteros positivos debajo de eso (excepto 1) para ver si son factores. Ejemplo es 111 primo?

Sqrt (111) está cerca de sqrt (100) = 10 y sqrt (121) = 11. Pero ni 10 ni 11 son factores de 111. Además, 2, 3, 4, 6, 7, 8 y 9 no son factores de 111. Por lo tanto, 111 es primo.

Answer 7

15 = 3 x 5, no es un número primo. si no supiéramos esto desde el principio, trataríamos de dividir 15 entre 2, y luego entre 3, etc. esa declaración básicamente dice que, para ver si 15 es primo o no, sería suficiente con 2 y 3 ( dado que la raíz de 15 es un número menor que 4, no necesitará probar un número mayor)

intentemos el peor de los casos, un número cuadrado. tome 49. no necesitaremos probar números superiores a 7 (49 ^ 0.5), y ahí es donde descubrimos que 49 no es primo.

para otro ejemplo, tomemos 641 (que tiene una raíz cuadrada de menos de 26). solo necesitamos tratar de dividir 641 por números entre 2 y 25, y si no encontramos divisores, entonces 641 es primo (que es).