# prime numbers!

## Recommended Posts

```\$okpass = 0
\$number = 1
\$limit = Int(InputBox( "the limit", "what would you lke to make the limit?"))

If \$limit < 0 Then
Do
\$limit = Int(InputBox( "the limit", "no negative numbers!"))
Until \$limit > 0
ElseIf \$limit == 0 Then
Do
\$limit = Int(InputBox( "the limit", "only whole numbers, and no letters!"))
Until \$limit <> 0
EndIf

ProgressOn("progress", "calculating primes...")
Do ; resets everything each time the number is increased
\$number += 1
\$tempnum = 1
\$no = 0
\$next = 0
\$evencheck = IsInt(number / 2)
isprime()
\$prog = (\$number / \$limit) * 100
ProgressSet(\$prog, \$number)
Until \$number >= \$limit

Func isprime() ; checks to see if the variable is a prime number using a loop, slow with numbers above 5 didgits, but better than nothing
If \$number <> 2 And \$evencheck == 1 Then
\$no == 1
EndIf
If \$number > 3 then
Do
\$tempnum += 1
\$test = \$number / \$tempnum
If IsInt ( \$test ) Then
\$no = 1
Else
\$next += 1
EndIf

If \$next >= (\$number / 2) Then
FileWrite(@ScriptDir & "\primenumbers.txt", \$number & ", ")
\$no = 1
EndIf
Until \$no == 1
Else
FileWrite(@ScriptDir & "\primenumbers.txt", \$number & ", ")
EndIf
EndFunc
ProgressSet(100, "all done!")
sleep(5000)
Exit```

Advise for improvements are much appreciated, the script has some efficiency issues atm, its very slow.

##### Share on other sites
```Local \$iBegin, \$sPrime = ""
Local \$iLimit = InputBox("The limit", "What would you lke to make the limit?", 1000)
If (Int(StringIsInt(\$iLimit)) + Int(StringIsFloat(\$iLimit)) > 0) Then
\$iBegin = TimerInit()
For \$x = 1 To \$iLimit
If _IsPrime(\$x) Then \$sPrime &= \$x & ", "
Next
ConsoleWrite("TIME: " & TimerDiff(\$iBegin) & @CRLF)
EndIf
If \$sPrime <> "" Then MsgBox(64, "Info", StringTrimRight(\$sPrime, 2))

Func _IsPrime(\$iNum) ; Alexander Alvonellos
If(\$iNum < 2) Then Return False
If(\$iNum = 2) Then Return True
If(BitAnd(\$iNum, 1) = 0) Then Return False
For \$i = 3 To Sqrt(\$iNum) Step 2
If(Mod(\$iNum, \$i) = 0) Then Return False
Next
Return True
EndFunc   ;==>_IsPrime```

Edited by johnmcloud
##### Share on other sites

Here's a version I wrote. I guess I can improve the code. It was an interesting challenge (the biggest step interval I ever used in a loop = 30030!).

If you look around the forum you will find more examples: https://www.autoitscript.com/forum/topic/164936-number-is-a-prime-number-challenge/

Edited by czardas
##### Share on other sites

Hi,

```Do ; resets everything each time the number is increased
\$number += 1
\$tempnum = 1
\$no = 0
\$next = 0
\$evencheck = IsInt(number / 2)
isprime()```

you should think about what you have written in your comments That´s one of the solutions for your "Speed"-problem.

There is no need to calculate every number isprime(). You better should use an algorithm which calculates the primes instead of test them with isprime().

A very fast and simple algorithm is the "Sieve of Eratosthenes"....have fun!

##### Share on other sites

Well thanks for the suggestions, I made it like 10x faster by using the square root function, and it now also calculates circle primes (primes that are still primes when their numbers are switched around) which I dont think any other script has done yet! what do you think of it now?

```\$okpass = 0
\$number = 1
\$limit = Int(InputBox( "the limit", "what would you lke to make the limit?"))

If \$limit < 0 Then
Do
\$limit = Int(InputBox( "the limit", "no negative numbers!"))
Until \$limit > 0
ElseIf \$limit == 0 Then
Do
\$limit = Int(InputBox( "the limit", "only whole numbers, and no letters!"))
Until \$limit <> 0
EndIf
\$circle = MsgBox(4, "test", "would you like to also record all the circle primes? circle primes are numbers that are still prime even when their numbers are switched around."); 6 == yes, 7 == no

ProgressOn("progress", "calculating primes...")
Do
\$ok = 0
\$number += 1
\$5check = String(\$number)
\$tempnum = 1
\$no = 0
\$next = 0
\$evencheck = IsInt(\$number / 2)
isprime()
\$prog = (\$number / \$limit) * 100
ProgressSet(\$prog, \$number)
Until \$number >= \$limit

Func isprime()
If \$number > 5 And StringRight(\$5check, 1) == 5 Then \$no = 1
If IsInt(Sqrt(\$number)) Then \$no = 1
If \$number <> 2 And \$evencheck == 1 Then
\$no = 1
EndIf
If \$number > 3 then
Do
\$tempnum += 1
\$test = \$number / \$tempnum
If IsInt ( \$test ) Then
\$no = 1
Else
\$next += 1
EndIf

If \$next >= Ceiling(sqrt(\$number)) Then
FileWrite(@ScriptDir & "\primenumbers.txt", \$number & ", ")
If \$circle == 6 Then iscircleprime()
\$no = 1
EndIf
Until \$no == 1
Else
FileWrite(@ScriptDir & "\primenumbers.txt", \$number & ", ")
EndIf
EndFunc
Func iscircleprime()
\$numstr = String(\$number)
\$lastchar = StringRight(\$numstr, 1)
\$numstr = StringTrimRight(\$numstr, 1)
\$numstr = \$lastchar & \$numstr
\$intnum = Number(\$numstr)
\$strlen = StringLen(\$numstr)
\$nextprime = 0
\$done = 0
\$up = 1
\$notgonnawork = 0
Do
\$numbercheck = StringRight(\$numstr, \$up)
Number(\$numbercheck)
If IsInt(\$numbercheck / 2) Then
\$notgonnawork = 1
Else
\$up += 1
EndIf
Until \$up >= \$strlen Or \$notgonnawork == 1
Do
\$intnum = Number(\$numstr)
\$evencheck = IsInt(\$number / 2)
\$ctempnum = 1
\$ok = 0
\$haha = 0
\$no = 0
If \$number < 10 Then
FileWrite(@ScriptDir & "\circleprimes.txt", \$number & ", ")
\$no = 1
\$ok = 1
EndIf

Do
If IsInt(Sqrt(\$intnum)) Then \$no = 1
\$ctempnum += 1
\$test = \$intnum / \$ctempnum
If IsInt ( \$test ) Then
\$no = 1
Else
\$haha += 1
EndIf

If \$haha >= Ceiling(sqrt(\$intnum)) Then
\$done += 1
\$lastchar = StringRight(\$numstr, 1)
\$numstr = StringTrimRight(\$numstr, 1)
\$numstr = \$lastchar & \$numstr
\$ok = 1
EndIf

Until \$ok == 1 Or \$notgonnawork == 1
If \$done == \$strlen Then
FileWrite(@ScriptDir & "\circleprimes.txt", \$number & ", ")
\$no = 1
EndIf
until \$no == 1 Or \$notgonnawork == 1
EndFunc
ProgressSet(100, "all done!")
sleep(5000)
Exit```

But I would really like to make it calculate primes then search for the circle primes in the prime numbers txt file, anyone know how I could do this? also sorry AndyG but I could not for the life of me figure out how to use  Sieve of Eratosthenes in the script :(.

*Edit: added 5 check, its a little faster now

**Edit: added thing that instantly rejects numbers that contain an even number in the circle function, its way faster now.

Edited by itsnotluketime
##### Share on other sites

I took a quick look. I see you are not taking advantage of the fact that all 2+ digit integers ending in 5 are not prime.

##### Share on other sites
1 minute ago, czardas said:

I took a quick look. I see you are not taking advantage of the fact that all 2+ digit integers ending in 5 are not prime.

Did not know that, I'll add it asap, thanks for the suggestion

##### Share on other sites

Yeah, I went through this logic. 15, 25, 35 etc... are not prime numbers. You can optimize speed by rejecting these numbers instantly.

Edited by czardas
##### Share on other sites

Just realized that the circle prime functions was seriously flawed, it did not work at all, sorry about that :(, but everything should work fine now.

Edited by itsnotluketime
##### Share on other sites
2 hours ago, czardas said:

all 2+ digit integers ending in 5 are not prime

A similar trick exists for divisibility by three:

Any number is divisible by three if the sum of its individual digits is divisible by three. (So 21 = 2+1 = 3 is divisible by three (7), and 123 = 1+2+3=6 is also divisible by three (41)).

My Contributions and Wrappers

Spoiler
##### Share on other sites

Also by 11: sum of digits in odd position = sum of digits in even position

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

That's cool. Now to formulate the proof (I have a gut feeling there's a really simple proof): failing that I'll cheat and look it up. ##### Share on other sites

Don't cheat, work it out by yourself for 3 and 11! This is your easy assignment for today This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

LOL, I have guitar lessons to prepare and teach. I like to cook these kind of ingredients on a slow heat. That's my way! Good tip though!

Edit : I think I got it, but you'll have wait for the solution [simple reductionism - starting with the premise that all numbers divisible by 3 are still divisible by 3 after you subtract 3 * 10^n].

Edited by czardas
##### Share on other sites

And here are some quick tests for divisibility by primes up to 50 (without proofs )

My Contributions and Wrappers

Spoiler
##### Share on other sites

Okay @jchd, you asked for the unschooled approach, and here it is:

Prove that when the sum of the digits of a number generate a product of 3, the number itself is also a product of 3.

30, 300, 3000 are each divisible by 3
10, 100, 1000 are each 1 higher than a number divisible by 3
20, 200, 2000 are each 1 lower than a number divisible by 3

Premise A
If X * 10^n is divisible by 3 then X is divisible by 3
:. trailing zeros can always be stripped leaving the same result
3 is a multiple of 3
1 is 1 higher than a multiple of 3
2 is 1 lower than a multiple of 3

Premise B
3 can always be subtracted from a multiple of 3 leaving a new multiple of 3
9 - 3 = 6
6 - 3 = 3
3 - 3 = 0

In accordance with Premises A and B, all numbers can be reduced to the digits 0, 1 & 2 (by subtracting 3 or 6 from each digit) without changing divisibility by 3.

It was shown that adding more zeros does not change the 3 possible outcomes.
01, 1, and 10 are each 1 higher than a number divisible by 3
02, 2, and 20 are each 1 lower than a number divisible by 3
:. zeros can be removed because they have no effect (tricky).

The following multi-digit sequences can also be removed (recursively):
12 can be removed repeatedly because it is divisible by 3 [1+2]
21 can be removed repeatedly because it is divisible by 3 [2+1]
111 can be removed repeatedly because it is divisible by 3 [1+1+1]
222 can be removed repeatedly because it is divisible by 3 [2+2+2]
If the number ends up with no digits, we have successfully subtracted multiples of 3 (* 10^n) leaving nothing at the end:

:. Regardless of size, all the numeric digits had to have added up to a multiple of 3 (in order to end up with nothing), in which case we know that the number we started with must also be divisible by 3.
QED (or big leap of faith)

Edited by czardas

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...