StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
2795148
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
3
CommunityOwnedDate
CreationDate
2010-05-08T18:19:23.790
FavoriteCount
0
LastActivityDate
2010-05-09T02:38:36.193
LastEditDate
2017-05-23T12:34:45.403
LastEditorUserId
-1
OwnerUserId
276101
ParentId
2795065
PostTypeId
2
Score
68
ViewCount
0
LastEditorDisplayName
text
Body
<p>I will explain the regex part outside of primality testing: the following regex, given a <code>String s</code> which consists of repeating <code>String t</code>, finds <code>t</code>.</p> <pre><code> System.out.println( "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1") ); // prints "Mamamia" </code></pre> <p>The way it works is that the regex captures <code>(.*)</code> into <code>\1</code>, and then sees if there's <code>\1+</code> following it. Using the <code>^</code> and <code>$</code> ensures that a match must be of the whole string.</p> <p>So, in a way, we're given <code>String s</code>, which is a "multiple" of <code>String t</code>, and the regex will find such <code>t</code> (the longest possible, since <code>\1</code> is greedy).</p> <p>Once you understand why this regex works, then (ignoring the first alternate in OP's regex for now) explaining how it's used for primality testing is simple.</p> <ul> <li>To test primality of <code>n</code>, first generate a <code>String</code> of length <code>n</code> (filled with the same <code>char</code>)</li> <li>The regex captures a <code>String</code> of some length (say <code>k</code>) into <code>\1</code>, and tries to match <code>\1+</code> to the rest of the <code>String</code> <ul> <li>If there is a match, then <code>n</code> is a proper multiple of <code>k</code>, and therefore <code>n</code> is not prime.</li> <li>If there's no match, then no such <code>k</code> exists that divides <code>n</code>, and <code>n</code> is therefore a prime</li> </ul></li> </ul> <hr> <blockquote> <p>How does <code>.?|(..+?)\1+</code> match prime numbers?</p> </blockquote> <p>Actually, it doesn't! It <a href="http://java.sun.com/javase/6/docs/api/java/lang/String.html#matches%28java.lang.String%29" rel="noreferrer">matches</a> <code>String</code> whose length is NOT prime!</p> <ul> <li><code>.?</code> : The first part of the alternation matches <code>String</code> of length <code>0</code> or <code>1</code> (NOT prime by definition)</li> <li><code>(..+?)\1+</code> : The second part of the alternation, a variation of the regex explained above, matches <code>String</code> of length <code>n</code> that is "a multiple" of a <code>String</code> of length <code>k >= 2</code> (i.e. <code>n</code> is a composite, NOT a prime). <ul> <li>Note that the reluctant modifier <code>?</code> is actually not needed for correctness, but it may help speed up the process by trying smaller <code>k</code> first</li> </ul></li> </ul> <p>Note the <code>!</code> <code>boolean</code> complement operator in the <code>return</code> statement: it negates the <code>matches</code>. It's when the regex <em>DOESN'T</em> match, <code>n</code> is prime! It's a double-negative logic, so no wonder it's kind of confusing!!</p> <hr> <h3>Simplification</h3> <p>Here's a simple rewriting of the code to make it more readable:</p> <pre><code>public static boolean isPrime(int n) { String lengthN = new String(new char[n]); boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+"); return !isNotPrimeN; } </code></pre> <p>The above is essentially the same as the original Java code, but broken apart into multiple statements with assignments to local variables to make the logic easier to understand.</p> <p>We can also simplify the regex, using finite repetition, as follows:</p> <pre><code>boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+"); </code></pre> <p>Again, given a <code>String</code> of length <code>n</code>, filled with the same <code>char</code>,</p> <ul> <li><code>.{0,1}</code> checks if <code>n = 0,1</code>, NOT prime</li> <li><code>(.{2,})\1+</code> checks if <code>n</code> is a proper multiple of <code>k >= 2</code>, NOT prime</li> </ul> <p>With the exception of the reluctant modifier <code>?</code> on <code>\1</code> (omitted for clarity), the above regex is identical to the original.</p> <hr> <h3>More fun regex</h3> <p>The following regex uses similar technique; it should be educational:</p> <pre><code>System.out.println( "OhMyGod=MyMyMyOhGodOhGodOhGod" .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!") ); // prints "Oh! My! God!" </code></pre> <h3>See also</h3> <ul> <li><a href="https://stackoverflow.com/questions/2565924/regular-expression-whos-greedier">Regular expressions: who's greedier</a></li> </ul>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHow to determine if a number is a prime with regex?
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USpolygenelubricants
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
2. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
3. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.