Sorry Ace, you've completely confused me here........ I'm glad of the extra information, but just a little overwhelmed and confused....
I may ramble a bit here, sorry! I'm just trying to get everything straight in my head, I've taken on a lot today!
---------------------------
The whole idea is to check for the highest prime factor of the number correct? I'm going to explain how I want my code to work in English a second:
- User inputs a number
- Perform isPrime function on original number. If the original number is prime, return true and output "Is Prime" and do no further processing
- If isPrime returns false, perform prime factor check
- Print the highest prime factor found by the prime factor checker
Does this make sense?
What I can't work out how to do is both the isPrime function and the Prime Factor check. Wait, that's effectively all of it :lol:
So, my original prime factor check worked as follows:
- Loop, starting from 3, until half of the original number
- If the original number divided by that factor is 0, then the currently found highest factor is that factor that the loop has just done. Divide the original number by that factor and store to variable
- Divide that new variable by the next factor and continue.
Typing that makes me realise that that code was flawed. I'm not quite sure exactly how, but in English it seems flawed....
------------------
I've come back to this post 1/2 an hour later now... Let's see where I am now:
I have made a simple prime checking function. This will be run when the number is imputed, to save processing if the number is already prime. I think I went about this inefficiently again, but your post confused me.
Code:
Private Function isPrime(ByVal num As Long) As Boolean
Dim limit As Long = CLng(num / 2)
If num Mod 2 = 0 Then
Return False
End If
For i As Long = 3 To limit Step 2
If num Mod i = 0 Then
Return False
End If
Next
Return True
End Function
I found working from smallest to largest was fastest because you're more likely to get a hit was smaller numbers earlier than if you worked from the number down to 3. So, now I have a program to check if something is prime... It actually works really quickly, even on the large number. It may not be the most efficient function, but it works quickly...
Code:
Option Strict On
Module Module1
Private Function isPrime(ByVal num As Long) As Boolean
Dim limit As Long = CLng(num / 2)
If num Mod 2 = 0 Then
Return False
End If
For i As Long = 3 To limit Step 2
If num Mod i = 0 Then
Return False
End If
Next
Return True
End Function
Sub Main()
Dim input As Long
Console.WriteLine("Enter a number")
input = CLng(Console.ReadLine)
Console.WriteLine("Is it prime? " & isPrime(input))
Console.ReadLine()
End Sub
End Module
Now I need to work on the prime factor checking part of it. Here is my plan, again, not sure if it's the best or not...
- Find square root of number
- Perform check as in original code, I think...
Oh, let's go with it, I'll compose the rest in a bit....
---------
Right, I'm stopping for tonight before I go insane.....
This is my code at this current point in time:
Code:
Option Strict On
Module Module1
Private Function isPrime(ByVal num As Long) As Boolean
Dim limit As Long = CLng(num / 2)
If num Mod 2 = 0 Then
Return False
End If
For i As Long = 3 To limit Step 2
If num Mod i = 0 Then
Return False
End If
Next
Return True
End Function
Private Function factorFinder(ByVal num As Long) As Decimal
Dim toCheck As Decimal = CDec(System.Math.Sqrt(num))
Dim factor As Long
Dim highestFact As Decimal = 1
toCheck = Math.Round(toCheck) + 1
For factor = 3 To CLng(toCheck) Step 2
If toCheck Mod factor = 0 Then
highestFact = factor
toCheck = toCheck / highestFact
End If
Next
Return highestFact
End Function
Sub Main()
Dim input As Long
Dim resultIsPrime As Boolean
Console.WriteLine("Enter a number")
input = CLng(Console.ReadLine)
resultIsPrime = isPrime(input)
Console.WriteLine(ControlChars.NewLine)
If resultIsPrime = True Then
Console.WriteLine("Original number was prime.")
Else
Console.WriteLine("Not prime")
Console.WriteLine(factorFinder(input))
End If
Console.ReadLine()
End Sub
End Module
It works with 13195, giving the answer as 29. But it gives the answer for 600851475143 as 775147, which isn't even divisible by 600851475143. 600851475143 / 775147 = 775145.19845010043256311383518223 ???????
---------------
YES!!! DONE IT!!! :-D :-D :-D :-D
It's far, far faster, completing in less than 1 second. It's only taken 2 hours to do!
My final code:
Code:
Option Strict On
Module Module1
Private Function isPrime(ByVal num As Long) As Boolean
Dim limit As Long = CLng(num / 2)
If num Mod 2 = 0 Then
Return False
End If
For i As Long = 3 To limit Step 2
If num Mod i = 0 Then
Return False
End If
Next
Return True
End Function
Private Function factorFinder(ByVal num As Long) As Decimal
Dim max As Decimal = CDec(System.Math.Sqrt(num))
Dim factor As Long
Dim highestFact As Decimal = 1
max = Math.Round(max) + 1
For factor = 3 To CLng(max) Step 2
If num Mod factor = 0 Then
highestFact = factor
num = CLng(num / highestFact)
End If
Next
Return highestFact
End Function
Sub Main()
Dim input As Long
Dim resultIsPrime As Boolean
Console.WriteLine("Enter a number")
input = CLng(Console.ReadLine)
resultIsPrime = isPrime(input)
Console.WriteLine(ControlChars.NewLine)
If resultIsPrime = True Then
Console.WriteLine("Original number was prime.")
Else
Console.WriteLine("Not prime")
Console.WriteLine(factorFinder(input))
End If
Console.ReadLine()
End Sub
End Module
Sorry for my babble and rambling!! If you've made it to this point, I am amazed!
OK Ace, I'm now less confused! :) What else can I do to my code to make it better??
Stephen