| dbo:abstract
|
- En matemàtiques i més concretament en teoria de nombres la Factorització per prova de divisions és un algorisme que troba un divisor no trivial d'un enter positiu si és que n'existeix cap. La idea consisteix a provar de dividir el nombre entre tots els divisors possibles fins a trobar-ne un que doni residu zero o veure que no n'hi ha cap. Si en troba algun llavors el nombre en qüestió és un nombre compost; altrament, és un nombre primer. Per tant l'algorisme de prova de divisions és tant un algorisme de factorització dels enters com una . Si un cop trobat un divisor, es divideix el nombre entre el divisor i es repeteix el procés amb el quocient, llavors s'arriba a la descomposició del nombre en factors primers. Per regla general s'utilitza aquest procediment només per trobar factors fins a un cert límit, llavors es parla de prova de divisions incompleta. (ca)
- القسمة المتكررة (بالإنجليزية: Trial division) هي الخوارزمية الأكثر صعوبة من أجل تفكيكك عدد ما إلى جداء أعداد أولية ولكنها أسهل خوارزمية من حيث الفهم. (ar)
- Die Probedivision ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven ganzen Zahl, wenn einer existiert. Findet er keinen solchen Teiler, so ist die vorgegebene Zahl eine Primzahl. Die Probedivision ist somit sowohl ein Faktorisierungsverfahren als auch ein Primzahltest. Führt man die Probedivision weiter, nachdem ein nichttrivialer Teiler gefunden wurde, so kann man letztendlich die Primfaktorzerlegung einer natürlichen Zahl ermitteln. In der Regel benutzt man dieses Verfahren nur als Faktorisierungsverfahren, um Primfaktoren bis zu einer gewissen Schranke zu finden. Man spricht dann von unvollständiger Probedivision. (de)
- Saiakuntzazko zatiketa zenbaki osoak faktorizatzeko algoritmoen artean errazen ulertzen dena da. Saiakuntzazko zatiketaren oinarrian dagoen funtsezko ideia honakoa da: faktorizatu beharrekoa n zenbaki osoa n baino txikiagoak diren zenbakiez zatigarria den ikustea. Adibidez, n=12 zenbaki osoaren zatitzaile bakarrak 1,2,3,4,6 eta 12 dira. Zenbaki lehenen potentzia handienak soilik hartuz, 12=3 x 4 adierazpena lortuko genuke. (eu)
- La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender. (es)
- En arithmétique, la méthode par divisions successives est la méthode la plus simple et la plus ancienne pour déterminer si un nombre entier naturel est premier (test de primalité) ou s'il est composé, pour en trouver la décomposition en produit de facteurs premiers. Cette méthode est utilisable en algorithmique. Très pratique pour tester de petits nombres, elle est peu efficace pour de grands nombres du fait de sa mauvaise complexité. (fr)
- Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than n. For example, for the integer n = 12, the only numbers that divide it are 1, 2, 3, 4, 6, 12. Selecting only the largest powers of primes in this list gives that 12 = 3 × 4 = 3 × 22. Trial division was first described by Fibonacci in his book Liber Abaci (1202). (en)
- 試し割り法(ためしわりほう、英: trial division)は最も面倒ではあるが、最も理解しやすい素数判定（素因数分解）アルゴリズムである。基本的な考え方は、素因数分解しようとする整数nを小さい順に割ってみて、割り切れるかどうかを調べる手法である。例えば、12という整数は、1, 2, 3, 4, 6, 12で割り切ることが可能である。 (ja)
- O algoritmo de divisão por tentativa (em inglês, Trial Division) é um método de força bruta para realizar a fatoração de números inteiros. Dado um número inteiro positivo , esse método consiste em verificar quais números inteiros menores do que são seus divisores. Também pode ser utilizado para testar a primalidade de um número. (pt)
- Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей. (ru)
- 试除法是整数分解演算法中最简单和最容易理解的演算法。首次出現於義大利數學家出版於1202年的著作。 给定一个合数n（这里，n是待分解的正整数），试除法看成是用小于等于的每个素数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是可分解整数的因數。试除法一定能够找到n的因數。因为它检查n的所有可能的因數，所以如果这个演算法“失败”，也就证明了n是个素数。试除法可以从几条途径来完善。例如，n的末位数不是0或者5，那么演算法中就可以跳过末位数是5的因數。如果末位数是2，检查偶数因數就可以了。 某种意义上说，试除法是个效率非常低的演算法，如果从2开始，一直算到需要次试除，这里pi(x)是小于x的素数的个数。这是不包括素性测试的。如果稍做变通——还是不包括素性测试——用小于的奇数去简单的试除，则需要次。这意味着，如果n有大小接近的素因數（例如公钥密码学中用到的），试除法是不太可能实行的。但是，当n有至少一个小因數，试除法可以很快找到这个小因數。值得注意的是，对于随机的n，2是其因數的概率是50％，3是33％，等等，88％的正整数有小于100的因數，91％的正整数有小于1000的因數。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9399 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- القسمة المتكررة (بالإنجليزية: Trial division) هي الخوارزمية الأكثر صعوبة من أجل تفكيكك عدد ما إلى جداء أعداد أولية ولكنها أسهل خوارزمية من حيث الفهم. (ar)
- Die Probedivision ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven ganzen Zahl, wenn einer existiert. Findet er keinen solchen Teiler, so ist die vorgegebene Zahl eine Primzahl. Die Probedivision ist somit sowohl ein Faktorisierungsverfahren als auch ein Primzahltest. Führt man die Probedivision weiter, nachdem ein nichttrivialer Teiler gefunden wurde, so kann man letztendlich die Primfaktorzerlegung einer natürlichen Zahl ermitteln. In der Regel benutzt man dieses Verfahren nur als Faktorisierungsverfahren, um Primfaktoren bis zu einer gewissen Schranke zu finden. Man spricht dann von unvollständiger Probedivision. (de)
- Saiakuntzazko zatiketa zenbaki osoak faktorizatzeko algoritmoen artean errazen ulertzen dena da. Saiakuntzazko zatiketaren oinarrian dagoen funtsezko ideia honakoa da: faktorizatu beharrekoa n zenbaki osoa n baino txikiagoak diren zenbakiez zatigarria den ikustea. Adibidez, n=12 zenbaki osoaren zatitzaile bakarrak 1,2,3,4,6 eta 12 dira. Zenbaki lehenen potentzia handienak soilik hartuz, 12=3 x 4 adierazpena lortuko genuke. (eu)
- La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender. (es)
- En arithmétique, la méthode par divisions successives est la méthode la plus simple et la plus ancienne pour déterminer si un nombre entier naturel est premier (test de primalité) ou s'il est composé, pour en trouver la décomposition en produit de facteurs premiers. Cette méthode est utilisable en algorithmique. Très pratique pour tester de petits nombres, elle est peu efficace pour de grands nombres du fait de sa mauvaise complexité. (fr)
- Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than n. For example, for the integer n = 12, the only numbers that divide it are 1, 2, 3, 4, 6, 12. Selecting only the largest powers of primes in this list gives that 12 = 3 × 4 = 3 × 22. Trial division was first described by Fibonacci in his book Liber Abaci (1202). (en)
- 試し割り法(ためしわりほう、英: trial division)は最も面倒ではあるが、最も理解しやすい素数判定（素因数分解）アルゴリズムである。基本的な考え方は、素因数分解しようとする整数nを小さい順に割ってみて、割り切れるかどうかを調べる手法である。例えば、12という整数は、1, 2, 3, 4, 6, 12で割り切ることが可能である。 (ja)
- O algoritmo de divisão por tentativa (em inglês, Trial Division) é um método de força bruta para realizar a fatoração de números inteiros. Dado um número inteiro positivo , esse método consiste em verificar quais números inteiros menores do que são seus divisores. Também pode ser utilizado para testar a primalidade de um número. (pt)
- Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей. (ru)
- 试除法是整数分解演算法中最简单和最容易理解的演算法。首次出現於義大利數學家出版於1202年的著作。 给定一个合数n（这里，n是待分解的正整数），试除法看成是用小于等于的每个素数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是可分解整数的因數。试除法一定能够找到n的因數。因为它检查n的所有可能的因數，所以如果这个演算法“失败”，也就证明了n是个素数。试除法可以从几条途径来完善。例如，n的末位数不是0或者5，那么演算法中就可以跳过末位数是5的因數。如果末位数是2，检查偶数因數就可以了。 某种意义上说，试除法是个效率非常低的演算法，如果从2开始，一直算到需要次试除，这里pi(x)是小于x的素数的个数。这是不包括素性测试的。如果稍做变通——还是不包括素性测试——用小于的奇数去简单的试除，则需要次。这意味着，如果n有大小接近的素因數（例如公钥密码学中用到的），试除法是不太可能实行的。但是，当n有至少一个小因數，试除法可以很快找到这个小因數。值得注意的是，对于随机的n，2是其因數的概率是50％，3是33％，等等，88％的正整数有小于100的因數，91％的正整数有小于1000的因數。 (zh)
- En matemàtiques i més concretament en teoria de nombres la Factorització per prova de divisions és un algorisme que troba un divisor no trivial d'un enter positiu si és que n'existeix cap. La idea consisteix a provar de dividir el nombre entre tots els divisors possibles fins a trobar-ne un que doni residu zero o veure que no n'hi ha cap. Per regla general s'utilitza aquest procediment només per trobar factors fins a un cert límit, llavors es parla de prova de divisions incompleta. (ca)
|
| rdfs:label
|
- قسمة متكررة (ar)
- Factorització per prova de divisions (ca)
- Probedivision (de)
- División por tentativa (es)
- Saiakuntzazko zatiketa (eu)
- Divisions successives (fr)
- 試し割り法 (ja)
- Перебор делителей (ru)
- Divisão por tentativa (pt)
- Trial division (en)
- 试除法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
