performance - Is this prime generator inefficient C++? -

-

is seen in efficient prime number generator. seems me pretty efficient. use of stream makes program run slower?

i trying submit spoj , tells me time limit exceeded... 

#include <iostream> #include <sstream>  using namespace std;  int main() {     int testcases, first, second, counter = 0;     bool isprime = true;     stringstream out;      cin >> testcases;      (int = 0; < testcases; i++) {         // next 2 numbers         cin >> first >> second;          if (first%2 == 0)             first++;          // find prime numbers between 2 given numbers         (int j = first; j <= second; j+=2) {             // go through , check if j prime             (int k = 2; k < j; k++) {                 if (j%k == 0) {                     isprime = false;                     break;                 }             }             if (isprime) {                 out << j << "\n";             }             isprime = true;         }         out << "\n";     }      cout << out.str();      return 0; }

edit: program supposed generate prime numbers between numbers specified in input. (see here more details: prime generator problem )

-tomek

this 1 step (skipping numbers) above naive algorithm. suggest sieve of eratosthenes more efficient algorithm. above link:

the complexity of algorithm o((nlogn)(loglogn)) memory requirement of o(n). segmented version of sieve of eratosthenes, basic optimizations such wheel factorization, uses o(n) operations , o(n1 / 2loglogn / logn) bits of memory.

the algorithm give somewhere near o(n^2). speedup skipping evens isn't great because find number not prime on first test. sieve has greater memory requirement, runtime complexity far superior large n.


Comments

Post a Comment

Popular posts from this blog

c++ - How do I get a multi line tooltip in MFC -

-
right now, have tool tip pops when hover on edit box. problem tool tip contains multiple error messages , in 1 long line. need have each error message on own line. error messages contained in cstring new line seperating them. my existing code below. bool ontooltiptext(uint, nmhdr* pnmhdr, lresult* presult) { assert(pnmhdr->code == ttn_needtexta || pnmhdr->code == ttn_needtextw); // need handle both ansi , unicode versions of message tooltiptexta* pttta = (tooltiptexta*)pnmhdr; tooltiptextw* ptttw = (tooltiptextw*)pnmhdr; // tchar szfulltext[256]; cstring strtiptext=_t(""); uint nid = pnmhdr->idfrom; if (pnmhdr->code == ttn_needtexta && (pttta->uflags & ttf_idishwnd) || pnmhdr->code == ttn_needtextw && (ptttw->uflags & ttf_idishwnd)) { // idfrom hwnd of tool nid = ::getdlgctrlid((hwnd)nid); } //m_errprojaccel[ch] contains 1 or more error messages each...
Read more

asp.net - In javascript how to find the height and width -

-
i having .aspx , masterpage page. in masterpage loading aspx page . in aspx page design using generating table structure using code-behind server in javascript how find height , width . regards, kumar if you're looking table height , width, should it var tbl = document.getelementbyid('tbldemo'); alert(tbl.offsetwidth + '\n' + tbl.offsetheight);
Read more

c# - DataTable to EnumerableRowCollection -

-
i have datatable according client requirement can contain invalid date "00/00/1999",null,empty string.(typed datset) when collect them enumerables wish convert of invalid forms empty string. (i.e) enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || (how check date invalid date) ? string.empty : order.field<datetime>("orderdate") } how check whether date valid date or not? datetime.tryparse...like given current code: datetime date; enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || !datetime.tryparse(convert.tostring(order.field<datetime...
Read more