New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using CSS to detect and counting Prime Numbers #12

Open
xieranmaya opened this Issue Jul 16, 2017 · 5 comments

Comments

Projects
None yet
2 participants
@xieranmaya
Owner

xieranmaya commented Jul 16, 2017

This post is translated from Chinese by me and my sister Tian Qiong, the main work is done by her and I would thank her much here!

In case you don't want to read all this, the final demo is here: https://xieranmaya.github.io/blog/css-prime.html, check the source code if you like.

Abstract

This article may involve below:

  • How to decide and select prime numbers
  • CSS counters and its scope
  • Pseudo elements
  • Generated content
  • Cascading Style
  • Flexbox layout

Inspiration

One day when I was reading the doc of nth-child pseudo-class, It occurs to me that whether the nth-child pseudo-class can be used to decide prime numbers. On the condition that it can be used to select the specific element that lies in every multiple of any number.

If I select all elements in the multiple location except themselves, the rest of the elements will be on the prime positions.

What an interesting thing! I write them down as soon as I thought of it. Here is the first version:

<style>
  li:first-child {
    color: grey;
  }
  li:nth-child(2n + 4) {
    color: grey;
  }
  li:nth-child(3n + 6) {
    color: grey;
  }
  li:nth-child(4n + 8) {
    color: grey;
  }
  li:nth-child(5n + 10) {
    color: grey;
  }
</style>
<ul>
  <li>01</li>
  <li>02</li>
  <li>03</li>
  <li>04</li>
  <li>05</li>
  <li>06</li>
  <li>07</li>
  <li>08</li>
  <li>09</li>
  <li>10</li>
</ul>

The above code turns all the elements that are not in the prime position into gray.

Notice that the parameter of the nth-child pseudo-classe is Xn + 2X instead of Xn + X, because n starts from 0. What we need to select is all X's multiples except for itself. So the min selected number is 2X. We only need to write until 5n + 10, because the multiples of 6 is more than 10.

All the above declaration block of selectors are the same, thus we can combine all the selectors into one combined selector.

<style>
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(4n + 8),
  li:nth-child(5n + 10) {
    color: grey;
  }
</style>
<ul>
  <li>01</li>
  <li>02</li>
  <li>03</li>
  <li>04</li>
  <li>05</li>
  <li>06</li>
  <li>07</li>
  <li>08</li>
  <li>09</li>
  <li>10</li>
</ul>

It looks much better now.

Highlight the prime numbers, Lowlight the non-prime numbers

The question is how to do if we want to highlight all the prime numbers. The selector in the above code didn’t select the prime numbers.

We can do it, easy. Make all the items red, and make non-prime number items into gray. Deal to the selector of non-prime number items have higher priority, thus make the prime numbers highlighted.

<style>
  /*优先级为 0,0,0,1*/
  li {
    color: red;
  }

  /*优先级为 0,0,1,1*/
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(4n + 8),
  li:nth-child(5n + 10) {
    color: grey;
  }
</style>
<ul>
  <li>01</li>
  <li>02</li>
  <li>03</li>
  <li>04</li>
  <li>05</li>
  <li>06</li>
  <li>07</li>
  <li>08</li>
  <li>09</li>
  <li>10</li>
</ul>

However a question remained, if we want to highlight all the prime numbers less than 100 by this method,the second combined selector would be 50 lines, it's too much.

Reduce the number of selectors

We can find through observation that: the li:nth-child(4n + 8) selector is not necessary to write: It chooses all the multiples of 4 except 4, but in fact li:nth-child(2n + 4) selector has selected all the 4's multiple items including 4. Similarly, we can deduce that if write li:nth-child(3n + 6) selector, it is not necessary to write li:nth-child(6n + 12), li:nth-child(9n + 18) etc. Selector that is the multiples of 3 in after n are all unnecessory to write.

Actually, if deleting all the unnecessary selectors, you will find that the coefficients before n are all prime numbers among the rest of selectors. If the coefficient before n is a non-prime number,all multiples of this non-prime number will be selected by the multiples of its prime factors. Namely, all multiples of a composite number is subset of the multiples of one prime factor, which makes all the coefficients before n that are composite number do not need to exist. This is similar to the screening method that we studied in primary school to find the prime numbers. And that's the screening process for the sieve of Eratosthenes method.

However, in order to filter more quickly,we can start from Xn + X * X to filter out the numbers for a factor X's multiples. Because if you have filtered out all the prime numbers multiples that are less than X, all the composite numbers smaller than X * X have been screened out. Since any composite number less than X * X must be able to find at least one prime number’s divisor less than X.

And based on the above rule, if we want to filter out all the prime numbers within M, we only need to filter out all the multiples of the prime number less than or equal to the square root of M.

Thus if we want to filter out all the prime numbers within 100, the following combined selector is enough:

<style>
  li {
    color: red;
  }
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(4n + 8),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14) {
    color: grey;
  }
</style>

The maximum prime number which is less than or equal to the square root of 100 is 7, so it is enough that our selector writes until li:(7n + 14).

Code Amount Complexity(I invented this word)

In fact, after a big circle around, the principle of prime screening was proved in another form.

As a conclusion, we only need the number of prime numbers within Sqrt(M) selectors to screening all the number less than M.

Then, there is another question, how many prime numbers less than a certain number? In fact, our predecessors have already studied this problem:

The number of prime numbers within n is about n/ln(n). The larger the number n, the number of prime numbers is closer to the value of this formula. See here for more info on Wikipedia: Prime Counting Functions.

So we can probably use O(sqrt(n)/ln(sqrt(n)) CSS codes(more specifially, selectors) to filter out all the prime numbers within n. As for prime numbers less than 1000, we only need a selector of 12 combined selectors:

<style>
  li {
    color: red;
  }
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14),
  li:nth-child(11n + 22),
  li:nth-child(13n + 26),
  li:nth-child(17n + 34),
  li:nth-child(19n + 38),
  li:nth-child(23n + 46),
  li:nth-child(29n + 58),
  li:nth-child(31n + 62) {
    color: #ddd;
  }
</style>
<ul>
  <li>01</li>
  <li>02</li>
  <li>03</li>
  <li>04</li>
  <li>05</li>
  ...
  <li>996</li>
  <li>997</li>
  <li>998</li>
  <li>999</li>
  <li>1000</li>
</ul>

In the above code, the pseudo-class selector parameters are not written to Xn + X * X, because the use of 2X will make our code amount less. Since square occupies more digits than its double, for example, 4 times 2 is 8 but the square of 4 is 16 which is longer then 8.

Automatic counting

The problem appearing again, the above code, we still have to put a number into the li tag. These tags can be generated with JS. But for a Obsessive-Compulsive Disorderd geek, it makes us uncomfortable. What’s more, I mentioned that we would use CSS to decide and select prime numbers.

You may think that we can replace the ul tag by ol tag. In that case, li tags' list marker will automatically be numbers. It does make sense, but it is difficult to control the list item numbers' style by CSS currently. For example, if I want adjust its position, there will be no method to take.

Besides, even if we use ul tag instead of ol tag, the li tags' list marker can also be set to numbers too. Namely, setting list-style-type attribute of li element to decimal or decimal-leading-zero is the answer.

So, is there any way to generate these numbers with CSS?

Sure, Of course there is.

We can use CSS counters and generated content to insert these numbers.

<style>
  li {
    /*遍历 DOM 的过程中,每遇到 li 就让 nature-count 计数器变量的值加一*/
    /*Every time we encounter li, we make nature-count++*/
    counter-increment: nature-count;
  }
  li::before {
    /*在 li 的 before 伪元素中插入计数器变量 nature-count 当前的值*/
    /*insert the counter value as generated content by pseudo element*/
    content: counter(nature-count);
  }
</style>
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>

The rendering result looks like below:

image

About CSS counter, you can refer to MDN documents here

Since it can count numbers, then I wonder if it can count the number of the prime numbers and non-prime numbers.

We can easily count the number of non-prime numbers, because the previous li:nth-child selector selected those non-prime items, and we only need to increase the counter by 1 when we meet them:

<style>
  li {
    counter-increment: nature-count
  }
  li::before {
    content: counter(nature-count);
  }
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14) {
    color: grey;
    counter-increment: nonprime-count;
  }
</style>
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>

However, the rendering results are not as same as we expected:

image

分析原因,我们会发现,是因为非素数选择器的 counter-increment 属性把 li 选择器对应的这个属性覆盖了,CSS 在发生属性覆盖时,是不会将两个相同属性值联合起来的,而是会选择最终生效的那一个,此处对于素数位置上的 li 元素,显然是 counter-increment: nonprime-count; 这一句会生效。所以导致了当解析器遇到合数位置上的 li 元素时,只给 nonprime-count 计数器加了一,知道了原因,就很好解决了,我们让遇到这个元素时同时给自然数计数器和非素数计数器都加一:counter-increment: nature-count nonprime-count;

Moving to the reasons, we find that because the counter-increment attribute of the non-prime selector overwrites the attribute corresponding the li selector, that is, when we encounter a li tag in a non-prime position, only the nonprime-counter will increase, but not nature-counter and nonprime-counter both increase. CSS won’t combine the same two attribute values when attribute is overwritten, and it will choose the one which its selector has higher proitity. Here, for the li element on the non-prime position, obviously is counter-increment: nonprime-count; which will take precedence. So when the parser encountered the li element on the position, it only plus one to the nonprime-count counter. It is easy to solve this after knowing the reason. We can plus one to the nature-count counter and nonprime-count counter if non-prime position li is encountered: counter-increment: nature-count nonprime-count;

And, we got the correct result:

image

Show statistical results

We can add a tag in the back of ul so that the statistics displayed in it.

<style>
  li {
    counter-increment: nature-count
  }
  li::before {
    content: counter(nature-count);
  }
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14) {
    color: grey;
    counter-increment: nature-count nonprime-count;
  }
  p::before {
    content: '' counter(nature-count) '个自然数中,有' counter(nonprime-count) '个合数' '' '' ;
  }
</style>
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>
<p></p>

But the results is out of our expectations again:

The two CSS counter variables obviously existed values, and it inserted into the li's pseudo element just now. Why it becomes a 0?

The scope of CSS counters

To understand this, we need to understand the concept of the scope of the CSS counters: the scope of a counter is only within the parent element of the outermost element that can have an effect on it.

In the above example, the count elements of the two counters are li, so these two counters are only valid within the parent element of the li, namely within ul. To solve this problem its also easy, we only need to make the outermost element affect the counter. We can make the counter to zero when encountering the body element, and in this way, this counter is available in the whole page:

<style>
  body {
    counter-reset: nature-count nonprime-count;
  }
  li {
    counter-increment: nature-count
  }
  li::before {
    content: counter(nature-count);
  }
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14) {
    color: grey;
    counter-increment: nature-count nonprime-count;
  }
  p::before {
    content: '' counter(nature-count) '个自然数中,有' counter(nonprime-count) '个合数' '' '' ;
  }
</style>
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>
<p></p>

OK, here is the result what we want

image

Now we have counted the number of natural numbers and the number of composite numbers, but how to know the number of prime numbers?
We all know that CSS can not do subtraction. Moreover, the two values exist in CSS counter, calc function can only implement the calculation of the hard coded literal value, and the results can’t directly display the value.

所以我们必须要找到一种让素数计数器递增的方法。这就意味着,我们必须使用选择器选出素数项才可以!
好像有点无能为力了,nth-child 选出非素数好办,但是选出素数,肯定没有能够实现这件事的选择器了。
然而

So we have to find a way to increase the prime number's counter, which means that we have to use the selector to select prime numbers!
It seems a bit hopeless, nth-child can easily select non-prime numbers. As for the election of prime numbers, there is certainly no selector can achieve this goal.

however----

Every cloud has a silver lining

We still have the not pseudo-class selector! Since we can use nth-child pseudo-class to select all the composite numbers, these selectors can act as not pseudo-class selector's parameters. In that case, all the prime numbers can be selected.

li:not(:first-child):not(:nth-child(2n + 4)):not(:nth-child(3n + 6)) {
  color: red;
  counter-increment: prime-count nature-count;
}

Pseudo-class selectors can be combined together, so we can combine some not pseudo-class selectors, and make the selector of the composite number to be not's parameters. By this method, the purpose of only selecting prime numbers can be achieved. And then we add a counter to the selector, in order to achieve the aim of counting the prime numbers.

Only the last question, that is, the statistics result is always displayed in the bottom. It works good if data is relatively small. But if data is large, it works not so good because you have to scroll to the page bottom if you want to see the statistics result.

Supposing that we move the p tag to the front of ul, the statistics data will show 0, because the value of each counter variable is still 0. This is why the p tag must appear behind ul in the DOM structure.

We can surely use the absolute positioning to move p tag to the top, but it is not so easy to control.

If you can ask the counter to have a value, as well as have no absolute positioning, besides let the contents of the p tag appears in front of ul, it would be nice.

There is still a method, that is we can use flex layout's order attribute. It can change the order of the elements displayed in the document while not changing the DOM structure. Because the counting of counter is only related to the DOM structure, it won’t affect the correctness of the statistical results.

The final code is as follows:

<style>
  body {
    /*用body元素的counter-reset属性重置三个计数器以使它们的作用域在整个body内*/
    /*make the counters global by reset them by body tag*/
    counter-reset: nature-count prime-count nonprime-count;
    display: flex;
    flex-direction: column;
  }

  li {
    list-style-type: none;
    display: inline-block;
  }

  /*在before伪元素中插入计数器的值以实现数值递增*/
  /*insert counter value into li tag*/
  li::before {
    content: counter(nature-count) ',';
  }
  li:last-child::before {
    content: counter(nature-count);/*最后一个元素不需要逗号分隔*/
    /*the last element do not neet a comma after it*/
  }

  /*合数项选择器*/
  /*non-prime selector*/
  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14) {
    /*递增自然数与合数计数器*/
    /*increase nature and non-prime counter*/
    counter-increment: nature-count nonprime-count;
    color: #ddd;/*合数变灰*/
    /*如果想只显示素数项,可以把合数全部隐藏起来*/
    /*display为none并不影响计数器的计数*/
    /*display: none;*/
  }
  /*素数项选择器*/
  /*prime selectors*/
  li:not(:first-child):not(:nth-child(2n + 4)):not(:nth-child(3n + 6)):not(:nth-child(5n + 10)) {
    /*递增自然数与素数计数器*/
    counter-increment: nature-count prime-count;
    color: red;/*素数变红*/
  }

  p {
    order: -1;/*让p元素显示在ul的前面*/
  }
  p::before {
    /*通过p标签的before伪元素插入统计结果*/
    content: '' counter(nature-count) ' 个自然数中,有 ' counter(nonprime-count) ' 个合数,' counter(prime-count) ' 个素数' ;
  }
</style>
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>
<p></p>

You can add any number of li tag at any time to the ul to display a wider range of prime numbers and statistical results without changing the code anywhere else.

Rendering results are displayed as follows, the subject is the rendering effect of 1000 numbers:

image

Complete demo is here: CSS Prime

@ghost

This comment has been minimized.

ghost commented Jul 26, 2017

Yeah I tried highlighting primes about 2 years ago and came up with a similar thing! https://codepen.io/matthewfelgate/pen/VYazKa?editors=1100

@ghost

This comment has been minimized.

ghost commented Jul 26, 2017

I suppose you could just use an <ol> ordered list to get the numbers.

I wonder if you could use selectors + css counter to only output prime numbers without hidding stuff?

@ghost

This comment has been minimized.

ghost commented Jul 26, 2017

Of course you could automate this bit with Sass:

  li:first-child,
  li:nth-child(2n + 4),
  li:nth-child(3n + 6),
  li:nth-child(5n + 10),
  li:nth-child(7n + 14)
@joezimjs

This comment has been minimized.

joezimjs commented Jul 28, 2017

The :not selector part is completely unnecessary. Just put it in the normal li styles and the li:nth-child... stuff will override it when it's not a prime number.

body {
  counter-reset: nature-count prime-count nonprime-count;
  display: flex;
  flex-direction: column;
}

li {
  list-style-type: none;
  display: inline-block;

  /* Everything for prime numbers can go here because non-primes will override it */
  counter-increment: nature-count prime-count;
  color: red;
}

li::before {
  content: counter(nature-count) ',';
}
li:last-child::before {
  content: counter(nature-count);
}

li:first-child,
li:nth-child(2n + 4),
li:nth-child(3n + 6),
li:nth-child(5n + 10),
li:nth-child(7n + 14) {
  counter-increment: nature-count nonprime-count;
  color: #ddd;
}

p::before {
  content: 'Count:' counter(nature-count) '; Non-Primes:' counter(nonprime-count) '; Primes:' counter(prime-count);
}
@xieranmaya

This comment has been minimized.

Owner

xieranmaya commented Jul 28, 2017

@joezimjs Wow, very clever idea!!! I have take a while understanding it~this is exactly how cascading works, thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment