Pega um ângulo qualquer BAC, marca em AC o tamanho 1 e o tamanho q, marca em AB o tamanho p, liga 1 até p, traça uma paralela a essa reta passando por q, você tem dois triângulos semelhantes, então o ponto onde a paralela termina é pq.
Por isso, embora construir um primo p usando a addition chain seja assintoticamente igual a log2p, um composto pode ser menos que isso (um primo pode ser menos que isso se tiver um composto perto e depois você soma ou subtrai algumas unidades? não sei).
Agora só fazendo uma força bruta pra calcular mesmo.
Nenhum comentário:
Postar um comentário