StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is an expansion on my take. It first checks if there is a <em>possible</em> factor in the list <code>div3</code>. If not, it adds candidates up to <em>number</em>/2, skipping values that already could be factored according to this list, so '37' and '43' get added, but not '36' or '39'.</p> <p>The above part should be considered "setup". If you know the input constraints (a maximum input value), you can calculate the vector <code>div3</code> once, then store it inside the program.</p> <p>If the list <code>div3</code> is up to date, the input should be factored into one of these numbers. If it can't then none of its factors contain a '3'. If it <em>can</em>, this shows the remainder, which can be factored further using conventional methods.</p> <p>I consider this "optimized" because the constraint "any factor should contain a '3'" is checked first. Only if <em>any</em> valid factor is found, you need to calculate all the others.</p> <p>My first program using <code><vector></code> and its ilk, so be gentle in your comments :-)</p> <p>(Edit) I now notice the factor checking loop goes over the entire <code>div3</code> vector. Of course, it only needs to go up to <code>number/2</code>. Left as an exercise to the reader.</p> <p>(Additional edit) <code>find3</code> is here a <em>reverse</em> iterator. For some reason that seemed appropriate, but I can't recall why I thought so :) If checking up to and including <code>number/2</code>, you need to change it to a regular forward iterator.</p> <pre><code>#include <iostream> #include <vector> using namespace std; int contains_3 (int value) { while (value && (value % 10) != 3) value /= 10; return value; } int main (int argc, char **argv) { int number, found_flag, last_div3, adjust, adjust_digit; vector<int> div3; vector<int>::reverse_iterator find3; vector<int>::iterator it; // a little seeding div3.push_back(3); div3.push_back(13); div3.push_back(23); if (argc != 2) return -1; number = atoi (argv[1]); found_flag = 0; // do we need to expand div3? last_div3 = div3.back(); while (last_div3 * 2 < number) { // if this number contains a '3' in any other place than the last, // simply increment it if ((last_div3 % 10) != 9 && contains_3(last_div3/10)) { last_div3++; } else { // no? then simply pick the next multiple of 10 and add 3 last_div3 /= 10; last_div3++; last_div3 *= 10; if (!contains_3(last_div3)) last_div3 += 3; } // check if it should be in the list for (it = div3.begin() ; it != div3.end() && (last_div3 % *it); ++it) ; if (it == div3.end()) { div3.push_back(last_div3); } } cout << "list is now: "; for (it = div3.begin() ; it != div3.end(); ++it) cout << ' ' << *it; cout << endl; for (find3 = div3.rbegin(); !found_flag && find3 != div3.rend(); find3++) { if (!(number % *find3)) { cout << "candidate: " << *find3 << ", remaining to sieve: " << number/(*find3) << endl; found_flag++; } } if (!found_flag) cout << "None found" << endl; return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload