Discussion :

[sandaff]

Bonjour tout le monde;

Il y a une question qui tarode l'esprit que j'aimerais savoir:

Sachant que nous ne connaisons pas les facteurs premiers d'un nombre composé impair, comment peut on encadrer soit le plus petit diviseur ou le plus grand diviseur; soit le deux?

Il y a t-il de possibilité de faire ce calcul sur ce nombre composé et les valeurs qui encadre soit plus proche du diviseur?

si N est le nombre et p et q les deux divisurs p superieur à q;
valinf<p<valsup ou valinf<q<valsup
ou les deux :
valinf1<q<valsup1 et valinf3<p<valsup4

Merci d'avance pour votre eclaircisement!

[Flodelarab]

Bonjour

À partir de 5, tous les nombres premiers sont de la forme 6n±1. On peut donc aller de 6 en 6. Le petit facteur est entre 2 et racine de N. Le grand facteur est entre racine de N et N.

[sandaff]

Merci pour votre intervention;

ça encadre mais pas très proche en prenant chaque nombre;

si c'est trop eloigner le calcul deviendra long qui n'arrangera pas.

[wiwaxia]

Bonjour,

... À partir de 5, tous les nombres premiers sont de la forme 6n±1. On peut donc aller de 6 en 6 ...

La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 21, 23 ...
conduit à des écarts alternativement égaux à 2 et 4, valeurs données par l'expression itérative x_k+1 = 6 - x_k ;
on les obtient par des instructions du type

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
d:= 1; e:= 4;
REPEAT
  d:= d + e; e:= 6 - e; ...
UNTIL <condition d'arrêt>

[Jipété]

Yep !

La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 21, 23 ...

21 !

[wiwaxia]

Bonjour

Exact. La suite des exemples était:... 19, 23, 25, 29, 31 ...

[Flodelarab]

Exact. La suite des exemples était:... 19, 23, 25, 29, 31 ...

25 ! 25 n'est-il pas le carré de 5 ?

[sandaff]

Bonjour,
La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 23 ...
conduit à des écarts alternativement égaux à 2 et 4, valeurs données par l'expression itérative x_k+1 = 6 - x_k ;
on les obtient par des instructions du type

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
d:= 1; e:= 4;
REPEAT
  d:= d + e; e:= 6 - e; ...
UNTIL <condition d'arrêt>

J'aime beaucoup votre intervention!

surtout merci pour tous ceux qui ont intervenu et j'espère que s'il y d'autre idées concernant ma question, une solution qui pourrait encadrer de tout près l'un des diviseurs premiers d'un nombre je serrai très ravis.

[wiwaxia]

... Sachant que nous ne connaissons pas les facteurs premiers d'un nombre composé impair, comment peut on encadrer soit le plus petit diviseur ou le plus grand diviseur; soit le deux?

Il y a t-il de possibilité de faire ce calcul sur ce nombre composé et les valeurs qui encadre soit plus proche du diviseur? ...

La recherche des diviseurs éventuels d'un nombre impair (N) exige de passer par l'énumération des entiers impairs ne dépassant pas (√N); en l'absence de toute information sur le nombre de départ, il n'existe malheureusement pas de raccourci par cadrage des solutions recherchées.

On a par exemple:
# 1000000000000009 = 179*5586592178771 (l'identification du plus petit diviseur est alors très rapide);
# 1000000000000003 = 14902357 * 67103479 (les calculs sont alors 83000 fois plus longs):
# 1000000000000037 est premier (il faut donc effectuer plus de dix millions de vérifications).

La seule amélioration envisageable est d'utiliser une suite comportant une plus forte densité de termes premiers, par ex. la suite définie par

d MOD 30 = {1, 7, 11, 13, 17, 19, 23, 29 ...} , valable au-delà de 5 .

Le gain obtenu (8/30 = 27% de candidats à la primalité au lieu de 2/6 = 33%) se révèle décevant au regard de la complication de l'algorithme ... mais on aborde là un autre sujet de discussion.