Existe-t-il un algorithme efficace pour déterminer la probabilité qu'un gros entier choisi de manière aléatoire n'est pas divisible par un entier d'un certain ensemble?

Question

donné un ensemble de 10 entiers $ a= a_1, a_2, \ cdots a_ {10} $ , y a-t-il un algorithme efficace qui peut me dire quelle est la probabilitéun entier choisi au hasard entre 1 $ $ et 10 $ ^ {10} $ n'est pas divisible par n'importe quel membre de cet ensemble.

Je comprends que le principe d'exclusion d'inclusion peut être utilisé pour résoudre ce problème, mais je ne peux pas comprendre comment la mettre en œuvre afin que cela fonctionne efficacement.

note : quand je dis "efficace", je veux dire du temps polynomial, mais je ne suis pas tout à fait sûr de ce qui se qualifie comme une période polynomiale est ce cas car les deux variables sont fixes.

Answer 1

let $ \ mathbf x $ être un nombre aléatoire dans la plage 1 $, \ ldots, n $ , et laissez $ e_i $ désignant l'événement que $ \ mathbf x $ est divisible par $ a_i $ . Vous êtes intéressé par la probabilité qu'aucun des événements $ E_1, \ LDOTS, E_M $ se produise (dans votre cas, $ m= 10 $ ). Utilisation du principe d'exclusion d'inclusion, cela réduit à calculer la probabilité des événements de la forme $ e_ {i_1} \ terres \ cdots \ terres e_ {i_k} $ , c'est-à-dire que $ \ mathbf x $ est divisible par tout $ a_ {i_1}, \ ldots, a_ {i_k} $ . Depuis une $ \ mathbf x $ est divisible par une bande de nombres IFF il est divisible par leur LCM, il suffit de déterminer la probabilité que $ \ mathbf x $ est divisible par $ A $ .

parmi 1 $, \ ldots, n $ , les chiffres divisibles par $ a $ sont $$ a, 2a, 3a, \ ldots, \ llfloor n / a \ rfloor a, $$ Dans Total $ \ LFLOOR N / A \ RFLOOR $ $ numéros. D'où la probabilité que $ \ mathbf x $ est divisible par $ a $ est exactement $$ \ frac {\ lflfor n / a \ rfloor} {n}. $$