prime numbers!

[itsnotluketime]

expandcollapse popup

$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.

[johnmcloud]

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 April 13, 2016 by johnmcloud

[czardas]

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!).
https://www.autoitscript.com/forum/topic/158400-resurrecting-a-2000-year-old-thread/?do=findComment&comment=1149851

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 April 18, 2016 by czardas

[AndyG]

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!

[itsnotluketime]

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?

expandcollapse popup

$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 April 20, 2016 by itsnotluketime

[czardas]

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.

[itsnotluketime]

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

[czardas]

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

Edited April 20, 2016 by czardas

[itsnotluketime]

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 April 20, 2016 by itsnotluketime

[RTFC]

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)).

[jchd]

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

[czardas]

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.

[jchd]

Don't cheat, work it out by yourself for 3 and 11! This is your easy assignment for today

 

[czardas]

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 April 20, 2016 by czardas

[RTFC]

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

[czardas]

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 April 20, 2016 by czardas