Inspired by @jinyao 's Java solution with building prime table, the key here is that only need to check number of subsegments `nSeg`

which is a prime divisor of `s.length()`

. Because if `s`

can be partitioned into `nSeg`

identical substrings, it can be definitely partitioned into `nSeg/d`

longer substrings which are concatenation of `d`

smaller substrings each.

```
bool repeatedSubstringPattern(string s) {
int n = s.size(); vector<bool> prime(n+1, true);
for (int i = 2; i <= n; ++i) {
if (n%i || !prime[i]) continue;
if (s.substr(n/i) == s.substr(0, n-n/i)) return true;
for (int j = 2; i*j <= n; ++j) prime[i*j] = false;
}
return false;
}
```