$max= 120; @primes= (); $tested might be better named something like $nonprime. Although we put 1 into the array to start with, it doesn't actually do anything useful... it could equally be left empty. Also, @tested isn't a list of non-primes, but a list of boolean values whose indices are...

c++,performance,algorithm,optimization,sieve-of-eratosthenes

Here is what I can say about the performance of your program: Likely your main problem is the call to std::sqrt(). This is a floating point function that's designed for full precision of the result, and it definitely take quite a few cycles. I bet you'll be much faster if...

If you want to get this approach working, you can do the fix advised by @Thierry to check count2 < n first in your while loop and then also surround the line numbers[count2] = 0 with an if clause to check count2 is not beyond the end of the index....

c,primes,sieve-of-eratosthenes

The problem is that you attempt to create an array isPrime on the stack that is larger than the available memory. You should create it on the heap instead, using bool *isPrime; isPrime = malloc((number + 1) * sizeof *isPrime); do this only once obviously, not for every call to...

Why use Sieve of Eratosthenes when you can Brute force all the way! #include <iostream> using namespace std; int main() { long long int num = 600851475143; int LPF = 1; int i; for (i = 2; i <= 600851475143 && num != 1; i++) { while (num % i...

performance,algorithm,c#-4.0,primes,sieve-of-eratosthenes

The smallest multiple of prime p greater than the bound lo is floor(lo/p)*p+p. You could use that for your starting point instead of starting from p.

c++,algorithm,sieve-of-eratosthenes

There's no major flaw in your code - it works, but it's a bit bulky. The basic logic is: Fill a vector, named sieve, with 1s (chars to save memory) For each prime element in the first vector, mark all of its multiples as prime Add every prime element int...

c,cuda,parallel-processing,primes,sieve-of-eratosthenes

This code has a variety of problems, in my view. You are fundamentally accessing items out of range. Consider this sequence in your kernel: int tid = threadIdx.x + 1; int offset = blockIdx.x * blockDim.x; int number = offset + tid; cache[tid - 1] = global[number]; You (in some...

prolog,primes,sieve-of-eratosthenes,prolog-coroutining

Ok i found out solution i had to change recursive call in sieve so now i call it in freeze predicate. as requested i found clue here Lazy lists in Prolog? sieve(N,L) :- sieve(L,Strumien,[]), numlist(2,N,X), X = Strumien. sieve(L,Strumien,X) :- freeze(Strumien, ( Strumien =[H|T], filter(H,T,Z), sieve(L,Z,[H|X]) )). sieve(L,[],L). filter(H,S,X) :-...

python-3.x,primes,sieve-of-eratosthenes,number-theory

Always try to measure empirical complexity of your code at several ranges. Your code is slow because of how you find the set difference, and that you always convert between set and list and back. You should be using one set throughout, and updating it in place with sete.difference_update(range(p*p,n,p*2)) To...

python,primes,infinite,sieve-of-eratosthenes,wheel-factorization

The odds, i.e. 2-coprimes, are generated by "rolling the wheel" [2], i.e. by repeated additions of 2, starting from the initial value of 3 (similarly from 5, 7, 9, ...), n=3; n+=2; n+=2; n+=2; ... # wheel = [2] 3 5 7 9 The 2-3-coprimes are generated by repeated additions...

algorithm,sieve-of-eratosthenes

According to the Wikipedia article on the subject, that particular sieve is still a very efficient method for producing the full list of primes whose value is less than a few millions. Also, the general idea of a sieve is used in several other, more powerful algorithms, such as the...

c++,algorithm,sum,primes,sieve-of-eratosthenes

I see two immediately obvious ways to speed up your algorithm. First, you are using 1000 * 1000 as the limit for your loops. Better to do the calculation once: big limit = 1000 * 1000; and use the variable limit in your loops. Depending on your compiler, you might...

The loop of the first function does 10 iterations for n = 100, the second function does 4. sieve <- function(n){ sq.n <- sqrt(n) vec <- 2:n primes <- rep(0, times=(sq.n)) i <- 1 while (!(is.na(primes[i] < sq.n)) && (primes[i]) < (sq.n)) { count <<- count + 1 primes[i] <-...

java,error-handling,heap-memory,sieve-of-eratosthenes

Opetion has already pointed out the several structural problems with your code; some bits of the program do not make any sense at all (like if (arr[a] == 1 && arr[a] >= m)). Not to mention that the code does not implement the Sieve of Eratosthenes, even though it uses...

c++,algorithm,primes,sieve-of-eratosthenes

Instead of bool primes[n + 1] = { 0 };, do: std::vector<bool> primes(n+1); This allocates non-stack space for enough primes, and initializes them all to false. This version has another advantage in that the compiler may specialize it to use one bit per value, whereas your version used one byte...

scanf("%lld %lld",&m,&n); prime=(int*)(malloc((n-m)*sizeof(int))) You are allocating memory for n-m elements and you are trying to access the mth to n-1 th element which is out of bound access which will lead to undefined behavior hence you are seeing a crash. There are similar other access in the same loop so...

python,lambda,primes,modulus,sieve-of-eratosthenes

It looks like a compact (but somewhat obscure) implementation of the Sieve of Eratosthenes [EDIT: as pointed out in the comments, this is in fact an "unfaithful sieve" as the trial division causes worse time complexity than the actual Sieve of Eratosthenes]. The first line is just an arbitrary search...

java,graphics,sieve-of-eratosthenes,stddraw

It looks like "scale" defines the user-coordinate system, so you need to calculate the dimensions of your sieve then set the coordinate system so the sieve's in the middle of it, perhaps with a bit of padding around it. You need something like this, in the main() method, before you...

c,algorithm,sieve-of-eratosthenes

for(i=2;primes[i]!=0&&i<=20;i++){ printf("%d\n",i); } Your primes[i]!=0 condition will cause the loop to terminate once it encounters a non-prime number, namely "4". Try separating it into its own conditional. for(i=2;i<=20;i++){ if (primes[i] != 0){ printf("%d\n",i); } } ...

c++,primes,sieve-of-eratosthenes

Following is a template hope it helps , it takes O(nlog(logn)) time and O(n) memory if you have to generate all primes from 1 to n void print_primes(int n) { int primes[n+1],start=2,i; /* Initialization , if primes[i]=1 it means i is prime and if 0 it means i is composite,...

list,haskell,primes,sieve-of-eratosthenes

what you call sieve is usually called minus, subtracting the second list from the first, assuming the both are ordered, increasing lists of numbers. then it is enough to compare just the two head elements, without any elem calls. but it could still work, had you provided a proper definition...

java,list,primes,sieve-of-eratosthenes

Your algorithm is not efficient. So regardless of which data structure you use you won't get a great performance speed-up. You should use another algorithm called 'Sieve of Eratosthenes'. Try to implement this algorithm and you'll notice the difference in performance (especially for bigger values of N). Currently you have...

c++,sieve-of-eratosthenes,factors

The hard limit on the arrays is set probably because the problem demands so? If not then just bad code. Inside the inner loop, you are calculating the largest power of a prime that divides the number. Why? See point 3. The number of factors of a number n...