Finding square roots

[Skyone]

if factorial of x then its prime? what?

'!' is 'not'.

[lifeisbetterwithketchup]

Code: Select all

    Function PrimeTest(ByVal x)
        prime = True
        If Not x = System.Math.Abs(x) Then
            prime = False
        Else
        Dim i As Integer
            i = 2
            Do Until i >= System.Math.Sqrt(x)
                If x Mod i = 0 Then
                    prime = False
                End If
                i = i + 1
            Loop
        End If
    End Function

Not the most efficient thing in the world (I'm not too good with efficiency in VB .NET, I'm taking a class on it right now), but it works.

[Skyone]

Instead of

Code: Select all

If x / i = Int(x / i) Then 

Use

Code: Select all

If x Mod i = 0 Then 

Mod is modular division, which is what % represents.

[ghosstt]

we havn't gotten to functions yet.. could you explain more

[lifeisbetterwithketchup]

Thanks, Sky.

ghosstt, to use functions, you put the code for the function right below "Inherits System.Windows.Forms.Form" in the code, then to run the function from a subroutine, you call it with for example "PrimeTest(31)".

[ghosstt]

ah, ok thanks

[bobbypig]

to test for a prime number, the fastest way is to have a list. Of course, that list gets pretty long, so you should only have primes under a million or so.
to find them, write a program to make an array for the prime numbers and a variable to keep track of what number it's on.

then have it go to every number (starting at two and ending somewhere high) and do the following:
try dividing it by every prime number in the array. If at any point the result is a whole number, skip to the next number
if the number isn't divisible by any primes less than it, you're looking at a prime number that should be added to the array.

the reason you don't have to divide by non-prime numbers is that they're all multiples of prime numbers.
for example, 12 isn't a prime number. you could find that by dividing by 6, but 6 is really just 2*3 (two prime numbers that would be tested)


If you have a big enough list, most numbers entered in will instantly have a result. Otherwise, your actual program could continue building the list until you get to your final number.

TIP: before starting up the list-making loop, you should test the entered number against primes in the original list. This will filter out obvious stuff like even numbers or multiples of 7 before you even start testing new numbers.

ANOTHER TIP: Nothing more than 1/(the highest prime you already have) of your number will need to be tested by the loop as you already would have found it.

so the final way of dealing with a number greater than the biggest number on your list is:
1. Divide it by all the numbers on your list starting at 2. If you get a whole number for any of them, it's not prime (break the loop).
2. Determine the greatest prime in your list and save it as a variable
3. Divide the inputed number by the greatest prime and save that as a variable (round up to be safe)
4 If the variable from step 3 is less than the one from step two, the inputed is prime (break the loop)
5. Start the prime number finding loop starting at the variable from step two plus one
6. If a prime number is found, divide the input by it. If you get a whole number, it's not prime (break the loop)
7. Once you've tested whatever the variable from step three is, you have a prime number (break the loop)


I hope this helps