itsnotluketime

prime numbers!

16 posts in this topic

$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 this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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 by czardas
1 person likes this

Share this post


Link to post
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 this post


Link to post
Share on other sites

#5 ·  Posted (edited)

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

#8 ·  Posted (edited)

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 this post


Link to post
Share on other sites

#9 ·  Posted (edited)

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 this post


Link to post
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)).

1 person likes this

Share this post


Link to post
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.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
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 this post


Link to post
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. :D

Share this post


Link to post
Share on other sites

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

 

1 person likes this

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
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 this post


Link to post
Share on other sites

#14 ·  Posted (edited)

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! :P 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 this post


Link to post
Share on other sites

#16 ·  Posted (edited)

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now