PureBasic Forums - English

Posted: **Sun Jul 21, 2013 3:59 pm**

i feel i should post this even i can't follow how it works since i have a severe Sore throat, it is about using regular expressions to check primality of numbers. look here
http://www.noulakaz.net/weblog/2007/03/ ... e-numbers/
http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

it will work for small numbers but not for a number like 1234567891 or 123456781 it will say it is prime even it is composite, this is because the capacity of string variable or the engine itself.
feel free to change it or to explain how it works

Code: Select all

number=13
sNum.s = LSet("1", number,"1") ; make string from 13 "1"'s
 
CreateRegularExpression(0, "^1?$|^(11+?)\1+$")
a = MatchRegularExpression(0, sNum) 
If a =0 
  Debug ("number = " + number + "  is prime")
Else
  Debug ("number = " + number + "  is not prime")
EndIf

Posted: **Sun Jul 21, 2013 5:13 pm**

this method is very slow to check a prime number.

the regular expression works like this:

13 wrote: 1.1111111111 = "1" -> false
11.11.11.11.11.11.1 = "11"*n -> false
111.111.111.111.1 = "111"*n -> false
1111.1111.1111.1 = "1111"*n -> false
...

15 wrote: 111111111111111 = "1" -> false
11.11.11.11.11.11.1 = "11"*n -> false
111.111.111.111 = "111"*n -> true
...

It is tested whether the number is divisible by 2,3,4,5, etc.

Posted: **Sun Jul 21, 2013 5:34 pm**

Hi applePi,

Thank you for a very interesting post!

It'll be a fun way of learning Regular Expressions.

PureBasic Forums - English

testing number primality using regular expression

testing number primality using regular expression

Re: testing number primality using regular expression

Re: testing number primality using regular expression