Quick & Dirty
 

I wrote my own piece of code to filter for candidates. I tried to stay away from built-in functions a best as possible.

[code]' If result = 0 then number is composite.

half = Fix(Sqr(number))

For denom = 2 To half
result = (number / denom) - Fix(number / denom)
If result = 0 Then
Exit For
End If
Next denom[/code]It works fine in my implementation of finding candidates within a range of numbers. It would be too slow for mass searching. The largest values I've tested with are over 10[sup]9[/sup].

What does "filter for candidates" mean? Do you mean "trial-factor integers"?

I have no idea what programming language that is, but it looks like it's doing a for-loop over 2,3,4,5,6,... and trial-dividing the input by those.

Again, you don't make clear what you mean by "built-in function", but I suspect "/" and "Fix" are no less built-in than "modulo".

Ever consider reading even some elementary number theory? (Hint: you can be more restrictive in your choice of potential divisors).

I have no idea what age you are ... just figured I'd try a little constructive commentary before R.D.Silverman finds this thread and tears you a new one, "kid".

It is VB .Net. What I put here is the core routine. Modulo has a limit so I work around it. I only pass numbers to this ending with 1, 3, 7, or 9 and increment in steps of two.

Built-in functions are Mod, Sqr, Int, an so on.

This is just something I experimented with. There is no way I can "trial factor" anything. That requires multiple-precision math, and only few programming platforms support it.

I am trying to learn a few things, not re-invent the wheel.

As for my age, I remember when JFK was president. I think that's close enough.

:smile:

[quote=storm5510;187399]
[code]' If result = 0 then number is composite.

half = Fix(Sqr(number))

For denom = 2 To half
result = (number / denom) - Fix(number / denom)
If result = 0 Then
Exit For
End If
Next denom[/code]
[/quote]
I think you will find MOD works for numbers up to 2^31 (about 2*10^9)
I use the same "get around" in QBasic.

But to test if the number is prime, you only need to check its
divisibility by prime numbers. Can you see why?
Google "Sieve of Eratosthenes" to see how to quickly and simply
generate a list of primes.

On a further programming note, you are asking for the
only heavy calculation (number/denom) to be performed twice.
Let quotient = number/denom
result = (quotient) - Fix(quotient)

David

PS As you noted, this routine is only appropriate for testing a few
numbers. To test a large range, you use the sieve principle again.

[quote=storm5510;187554]It is VB .Net. What I put here is the core routine. I only pass numbers to this ending with 1, 3, 7, or 9 and increment in steps of two.
[/quote]

Since you have tested for divisiibility by 2, an obvious way
to halve the time taken by your "core" routine is:

For denom = 3 To half Step 2

BTW "trial-factoring" is exactly what you are doing.

I can remember Ike:smile:

[quote]Google "Sieve of Eratosthenes" to see how to quickly and simply
generate a list of primes.[/quote]I have seen that page before. I couldn't see a way to convert it into code, but I'll look again.

What that line of code does is to strip away the whole number and only leave the fraction, if there is one.

I was born when Ike was president. :smile:

[URL]http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes[/URL]

[code]Eratosthenes(n) {
a[1] := 0
for i := 2 to n do a[i] := 1
p := 2
while p2 < n do {
j := p2
while (j < n) do {
a[j] := 0
j := j+p
}
repeat p := p+1 until a[p] = 1
}
return(a)
}[/code]At first, I thought this was Pascal, then I saw the braces. What is the significance of a[1]. Is this an array of some sort?

I can decipher it, but it will take a while. Not all that familiar with C++.

[quote=storm5510;187664][code]Eratosthenes(n) {
a[1] := 0
for i := 2 to n do a[i] := 1
p := 2
while p2 < n do {
j := p2
while (j < n) do {
a[j] := 0
j := j+p
}
repeat p := p+1 until a[p] = 1
}
return(a)
}[/code]At first, I thought this was Pascal, then I saw the braces. What is the significance of a[1]. Is this an array of some sort?

I can decipher it, but it will take a while. Not all that familiar with C++.[/quote]

It is pseudo-code... not meant to compile in any specific language but using constructs most languages support. a[i] means the ith element of array a.

I might be able to provide reasonably good VB.net Sieve of Eratosthenes code. I will have a look. It might end up being in c# though.

edit: found it just need to tidy it up and i think i just noticed an improvement
i need to reinstall vb.net 2008 express edition shows how long it is since i last programmed vb.net
i use c# now

here is my Sieve of Eratosthenes code:
[code]
Dim maxvalue As Int32 = 10000000
Dim primesarray As New BitArray(maxvalue)
primesarray.SetAll(True)
For i As Int32 = 2 To maxvalue - 1
If primesarray(i) = True Then
For j As Int32 = i + i To maxvalue - 1 Step i
primesarray(j) = False
Next
End If
Next
[/code]
the max size of a BitArray is the limit for maxvalue in this version