Programme de jugement des nombres premiers le plus rapide C # Java C ++

Un programme qui détermine si un nombre est un nombre premier ou un nombre non primaire. (Prend en charge C #, Java, C ++) Je l'ai fait parce que cela apparaît souvent comme un problème dans les concours de programmation tels que CodeIQ.

Programme de jugement des nombres premiers le plus rapide

Version C

public static bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Exclure les nombres pairs à l'avance

    double sqrtNum = Math.Sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            //Pas un nombre premier
            return false;
        }
    }

    //Est un nombre premier
    return true;
}

Si possible, je veux garder le code dans la plage que je peux comprendre, donc je l'utilise actuellement comme la version la plus rapide. (C'est facile, non?) Cependant, je pense que cette vitesse est suffisante pour résoudre le problème. Si cela ne suffit pas, détrompez-vous.

• "Eh, c'est un service, apportez aussi des implémentations Java et C ++!" * (Presque pareil)

Version Java

public static boolean isPrime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Exclure les nombres pairs à l'avance

    double sqrtNum = Math.sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            //Pas un nombre premier
            return false;
        }
    }

    //Est un nombre premier
    return true;
}

Version C ++

#include <math.h> 

bool IsPrime(int num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; //Exclure les nombres pairs à l'avance

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			//Pas un nombre premier
			return false;
		}
	}

	//Est un nombre premier
	return true;
}

• Version Java Je ne l'ai pas lancé, mais je pense que ça va. .. *

Explication des termes mathématiques

Je vais expliquer brièvement les termes que je n'ai pas compris.

• Qu'est-ce qu'un nombre premier? → Un entier naturel qui n'est pas divisible par des nombres autres que 1 et vous-même
• Qu'est-ce qu'un nombre composé? → Nombres autres que les nombres premiers

Explication de l'algorithme le plus rapide

Pour l'algorithme mis en œuvre, je me suis principalement référé au contenu de ce site. Jugement du nombre premier|Algorithme et structure des données| Aizu Online Judge

Sur ce site ** Dans le jugement des nombres premiers, la propriété que «le nombre composé x a un facteur premier p qui satisfait p ≤ √ x» peut être utilisée. ** ** Il y a une description, "Le nombre composé x a un facteur premier p qui satisfait p≤√x" = "Si x est un nombre composé, il a une fraction inférieure ou égale à √x" </ u> En d'autres termes, la condition de fin de boucle dépend de Math.Sqrt (num). Par rapport à la simple exécution du calcul du reste jusqu'à num, le nombre de boucles est réduit et la vitesse de traitement est considérablement réduite.

private static bool IsPrime(int num)
{
    if (num < 2) return false;

    for (int i = 2; i < num; i++)
    {
        if (num % i == 0)
        {
            //Pas un nombre premier
            return false;
        }
    }

    //Est un nombre premier
    return true;
}

private static bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Exclure les nombres pairs à l'avance

    for (int i = 3; i < num; i+=2)
    {
        if (num % i == 0)
        {
            //Pas un nombre premier
            return false;
        }
    }

    //Est un nombre premier
    return true;
}