Topic: Improvements of the Prime algorithm in QuickBasic

February 18, 2016

It is not necessary for each divisor to be checked all the way up to the user's number.

If there are any factors of the number above the square root of the number, then there must also be a factor equal to or less than the square root.
Altered determineIfPrime function to implement checking only up to the square root:


FUNCTION determineIfPrime (number)

    prime$ = "True"

    IF number = 0 OR number = 1 THEN

        prime$ = "False"

    ELSE

        divisor = 2

        WHILE divisor <= SQR(number)

            remainder = modulo(number, divisor)

            IF remainder = 0 THEN
                prime$ = "False"
            END IF

            divisor = divisor + 1

        WEND

        determineIfPrime = prime$

    END IF

END FUNCTION

It is not necessary keep checking for factors once the first one is found.

Once a remainder of 0 is found, the current divisor must be a factor of the user's number, which means the number is not prime.
Altered determineIfPrime function to implement stopping the loop once prime goes true, indicating the first factor has been found:


FUNCTION determineIfPrime (number)

    prime$ = "True"

    IF number = 0 OR number = 1 THEN

        prime$ = "False"

    ELSE

        divisor = 2

        WHILE prime = "True" AND divisor <= SQR(number)

            remainder = modulo(number, divisor)

            IF remainder = 0 THEN
                prime$ = "False"
            END IF

            divisor = divisor + 1

        WEND

        determineIfPrime = prime$

    END IF

END FUNCTION

It is not necessary to check any even divisors above 2.

If two is a factor, it means the number is even. It is not necessary to check possible even factors above 2.
Altered determineIfPrime function to implement checking 2, but no other even divisors:


FUNCTION determineIfPrime (number)

    prime$ = "True"

    IF number = 0 OR number = 1 THEN

        prime$ = "False"

    ELSE

        divisor = 2

        remainder = modulo(number, divisor)

        IF remainder = 0 THEN
            prime$ = "False"
        END IF

        divisor = 3

        WHILE prime = "True" AND divisor <= SQR(number)

            remainder = modulo(number, divisor)

            IF remainder = 0 THEN
                prime$ = "False"
            END IF

            divisor = divisor + 2

        WEND

        determineIfPrime = prime$

    END IF

END FUNCTION