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,...

You need to use raw_input for python2, input in python2 is basically eval(raw_input()) and as you have no variable okay defined you get the error. In [10]: prime = (str(input("\n"))) foo --------------------------------------------------------------------------- NameError Traceback (most recent call last) <ipython-input-10-15ff4b8b32ce> in <module>() ----> 1 prime = (str(input("\n"))) <string> in <module>() NameError:...

c#,math,primes,prime-factoring

I think, by the nature of the algorithm, there's no direct way to check if N is prime. To check if N is prime, first, you can use the easy divisors (2, 5, 7, etc), then you can generates all the Atkin primes under N, and then try to divide...

sqrt method input parameter needs to be a Double. So you need to cast it to Double. You will also need to use the math method called ceil. In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following...

security,certificate,primes,prime-factoring

As noted in my comment, RSA keys are usually way larger in size. Your examples can be brute forced easily (!). RSA keys as used for SSH and similar are usually 2048 or even 4096 bit long (approx 616 resp. 1233 decimal digits). At that point, trying to brute-force them...

haskell,list-comprehension,primes,infinite

In general, there's no problem with taking tails of primes, because Haskell is lazy (the evaluation is on-demand). Here specifically there's even less problem because each sublist is trimmed with under 100 = takeWhile (< 100) - only a finite prefix is taken. (x:xs) <- tails primes just goes through...

performance,haskell,time-complexity,primes,sieve

Your code has an exponential explosion inside it: sieve p (x:xs) | rem x p == 0 = sieve p xs | otherwise = x : (sieve x $ sieve p xs) -- ^^^^^^^ here! -- ^^^^^^^ and here! You intended for the inner sieve call to just continue filtering...

ruby-on-rails,ruby,primes,factorization

"premature optimization is (the root of all) evil". :) Here you go right away for the (1) biggest, (2) prime, factor. How about finding all the factors, prime or not, and then taking the last (biggest) of them that is prime. When we solve that, we can start optimizing it....

If you find all divisors(including the primes) of n are say a,b,c,d...h. If a divisor h > sqrt(n) exists, then some divisor c must also exist such that h * c = n and since h > sqrt(n) and h * c = sqrt(n) * sqrt(n) c < sqrt(n). So,...

Your program does not stop after it found those first few primes, but it runs into an infinite loop, generating no more output. The reason for this is that if your isprime check fails, you never increment the candidate_prime variable! Also, as noted in comments, you should compare num_ofprimes to...

python,performance,algorithm,time-complexity,primes

The Sieve of Eratosthenes looks like this: def sieve(n): primality_flags = [True]*(n+1) flags[0] = flags[1] = False primes = [] for i, flag in enumerate(primality_flags): if flag: primes.append(i) for j in xrange(2*i, n+1, i): flags[i] = False It processes each number once when the outer loop reaches it, and once...

f(x) = number of primes less than x f(x) can be approximated by x/logx. There are better but more complicated approximations, but a function for calculating this exactly is not known yet. ...

There is always the neat and newbie friendly regular expressions way of finding prime numbers: $n = $_GET['n']; echo "$n is ", preg_match('/^1?$|^(11+?)\1+$/', str_repeat('1', $n)) ? "not " : "", "a prime number", PHP_EOL; No seriously, what I would suggest is that you tidy up your code a bit, so...

See the comments on your post to find out why your code doesn't work. I'm just here to fix your code. First of all, make use of functions. They make code so much more readable. In this case, a function to check if a number is a prime would be...

javascript,html,arrays,primes,factors

In the special cases of 0 and 1, don't bother with the for loop, since you know what the correct results should be. So put the if outside the for: if (thenumber < 2) { array[0] = thenumber; } else { for (var i = 1; i <= thenumber; i++)...

java,optimization,out-of-memory,primes

There are two possibilities: You use -Xmx256M which means a 256 MB heap. But there's more than just the heap and your VM may get killed when it tries to get more. You give 256 MB to your VM but your program needs more and gets killed. <---- As RealSkeptic...

You can use List Comprehension, like so: for x in [prime in P if prime<=math.sqrt(p)]: ... ...

Got a good idea for your implementation: @primes = [] def prime_numbers(n) i = 2 while @primes.size < n do @primes << i if is_prime?(i) i += 1 end @primes end def is_prime?(n) @primes.each { |prime| return false if n % prime == 0 } true end This is based...

I can't think of anything better than the Sieve of Eratosthenes for what you want, so here is what I'd do. The Sieve of Eratosthenes only requires checking for prime divisors of a number up to the square root of that number, so you need not create an array for...

python,random,generator,list-comprehension,primes

It's better to just generate the list of primes, and then choose from that line. As is, with your code there is the slim chance that it will hit an infinite loop, either if there are no primes in the interval or if randint always picks a non-prime then the...

Only update primes when it's actually needed. Keep track of the number of entries you've updated, and only output that number of entries at the end: j := 0; for i := 0 to 999 do begin if candidates[i] <> 0 then begin primes[j] := i; Inc(j); end; end; for...

What I want to do is perhaps create a while loop that would eliminate the other multiples of the number leaving the prime numbers only. Although, I am not exactly sure how to achieve this, if anyone has any suggestions, I would greatly appreciate it. The algorithm you want...

python,algorithm,primes,algebra

If we find an intermediate result that is congruent to 1 (modulo n) and such that the previous result x was not congruent to 1 or -1 (i.e. n-1) modulo n, then this number x is a nontrivial square root of 1 modulo n (i.e. a number x such that...

python,list-comprehension,primes

As you want False if any lesser number is a divisor, code it directly that way: def isPrime(n): return n<=1 or not any(i for i in range(2, int(n ** 0.5) + 1) if n % i == 0) Note that this uses a genexp, not a listcomp, because that allows...

the original post, contained some misunderstandings.. here is a suggested fix: public class Number { public static HashSet<Integer> pSet; static { pSet = new HashSet<>(); pSet.add(2); } public static boolean isPrime(int n) { boolean out = true; if (n == 1) { return true; } if (pSet.contains(n)) { return true;...

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) :-...

java,algorithm,recursion,primes,prime-factoring

You can add f as an argument by overloading, and adding private method that does take it, and is invoked from the "main" public method. In the private method, you have 3 cases: stop clause: n==1: create a new empty list n%f == 0: recurse with n'=n/f, f'=f, and add...

actionscript-3,flash,primes,factorization,factors

Try this : function prime_factorization( n:int ): Array { var a:Array = [] ; for (var i:int = 2; i <= n / i; i++) { while (n % i == 0) { a.push(i) ; n = n / i ; } } if (n > 1) a.push(n) ; return...

You don't return when checking for num < 2. You could change to: if num < 2: print(num, "isn't a prime number") return assuming that you are in a function. Otherwise you could use else: if num < 2: print(num, "isn't a prime number") else: for x in range(2, num):...

python,algorithm,primes,python-3.4

Here is a much faster version primes = [] primecount = 0 candidate = 2 while primecount<50: is_prime = True for prime in primes: if candidate%prime == 0: is_prime = False break elif candidate < prime**2: break if is_prime: primes.append(candidate) primecount += 1 candidate += 1 print primes[-1] note small...

python,dictionary,global-variables,primes

d += {num2:primes} is ambiguous to python. d is a local on the left hand side and a global on the right hand side. You can fix the problem by putting global d at the top of the function. def dict_check(num) : global d ... ...

Is this what you want? int findprime(int low, int high) { int n, count, i; count = 0; n = 0; if (low <= 3) count = count + 1; while (n < low) n = n + 6; while (n < high) { int check; i = 1; check...

Here is a very simple solution: let's assume that the number that is present twice is x. Then the answer is {x, 1, 2, 3, ..., n - 1}. Why does it work? gcd(x, 1) = 1 for any x and gcd(a, a + 1) = 1 for any a....

You need to start your for loop at 3, not 1. everything is evenly divisible by 1, you already tested for division by 2. There are multiple things wrong with your code. The j counter is one of them. Looping including $nombre is also one. function Test-Prime { param( [Parameter(ValueFromPipeline=$true)]...

Your loop tests for j%k == 0, but k is always greater than j because your loop for k starts at j+1 and keeps getting bigger, so j%k will always equal j. I think your loop should be for(var k=j-1; k>1; k--) { if(j%k == 0) { primeArray[j]=0; break; //...

c#,linq,optimization,parallel-processing,primes

This does it nicely on my machine. I've never actually seen all my cores go to 100% until now. Thanks for giving me an excuse to play :) I increased the numbers until I had a time slow enough to measure (20,000). The key option that made the difference to...

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...

function,python-2.7,debugging,primes

You don't return the result for any value greater than 2. For 0, 1 and 2, you do return it: return True For the fourth case that covers all other numbers, you only print the result, but you don't return it as a boolean value. Edit: Your attempt to filter...

I suggest you to make separate functions for finding primes and displaying primes, so you will have more control on displaying those primes: #include <stdio.h> #include <math.h> // sqrt int is_prime (int x); void prime(int limit, int col); int main () { int limit, col; printf("Table of Primes\n"); printf("===============\n"); printf("Upper...

This creates a list of data frames formed by cutting the 8 columns of the built in data frame anscbome into 3 unequal sets: k <- 3 nc <- ncol(anscombe) lapply(split(as.list(anscombe), cut(1:nc, k, labels = FALSE)), as.data.frame) ...

for(i=0; i*i<m; i++){ if(m%i==0){ i starts as 0, so in m % i, you are dividing a number by zero....

javascript,html,if-statement,for-loop,primes

You should exit out of the loop as soon as you know that it's not a prime, otherwise the result will be overwritten in the next itaration. There is actually no point in having the else clause (as it just sets the same value over and over), just set that...

The function is not vectorized. Try primefindlist<-function(x){ return(x[x==2 | sapply(x, function(n)all(n %% seq(2,ceiling(sqrt(n)),by=1) !=0))]) } or primefindlist<-function(n){ return(n[n==2 | all(n %% seq(2,ceiling(sqrt(n)),by=1) !=0)]) } vPrimefindlist <- Vectorize(primefindlist, vectorize.args = "n") vPrimefindlist(c(7,11)) ...

Your for loop is looking for factors starts with i=1, and if index%i==0 you decide it is not a prime. But n%1==0 for all integers n. The lowest factor that indicates that something is not prime is 2. Edit: Here are some other suggestions: Use a properly bounded loop to...

The problems with your code are that you're repeatedly doing some expensive computation in the call functools.reduce(operator.mul, factorlist, 1) and that you're repeatedly checking isprime(x) for the same numbers (and isprime is itself expensive because of the loop). To avoid the functools.reduce call you can simply divide out the already...

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.

You can use Ruby's built in #prime? method, which seems pretty efficient. The code: require 'prime' primes_arr = (3..104729).to_a.select &:prime? runs in 2-3 seconds on my machine, which I find somewhat acceptable. If you need even better performance or if you really need to write your own method, try implementing...

objective-c,loops,for-loop,primes

The first loop starts p=2, then the inner loop take d=2 and then check if d<p. This condition is false because d=2 P=2. This means the first inner loop doesn't run and isPrime is always true at the first loop of p.

string.gmatch returns a string, you need to convert it to number before doing calculations Btw, you are doing the prime validation twice on your loop. This is a fixed version (returns 10 as expected): ... function sumOfPrimes(num) local sum = 0 for digit in string.gmatch(num, "%d") do digit = tonumber(digit)...

Hi use this code and problem is with your logic. public static void main(String[] args) { int i = 0; int num = 0; List<Integer> primes = new ArrayList<Integer>(); for (i = 1; i <= 100; i++) { int counter = 0; for (num = i; num >= 1; num--)...

When you use the method invocation syntax, i.e., Math::Prime::Util->random_strong_prime(128); the first argument to random_strong_prime becomes the string "Math::Prime::Util" which is not a positive integer. With method invocation syntax, 128 becomes the second parameter. The syntax you are using is appropriate for invoking a class method. Instead, you want to use...

Check MSDN about for keyword : Every for statement defines initializer, condition, and iterator sections. These sections usually determine how many times the loop iterates. So the second part is a condition and must be implicitly converted to bool. Since long type cannot be converted implicitly, u get a compile...

The reason this happens is that the expression that you use for the array size, i.e. sizeof(list)/sizeof(int) is a constant expression. Its value is not dependent on the allocated array pointed to by the list pointer. You need to store the allocated size separately to make this code work: if(...

The main bug is here: x = int(math.sqrt(x)) You are altering x, so the subsequent divisibility checks incorrectly use this altered value of x. You should store the square root in a different variable: sqrt_x = int(math.sqrt(x)) while i < sqrt_x + 1: ... Also, the number 2 is prime...

Here the code then the proposed solution for you thanks! #include <stdio.h> #include <stdlib.h> #include <time.h> #include <gmp.h> main() { mpz_t b; mpz_init(b); int escero; unsigned long numero,a; … printf("Introduzca el numero a testear\n"); scanf("%lu",&a); numero=a; srand((unsigned int)time(0)); mpz_t A,P,P1; mpz_init(A); mpz_init(P); mpz_init(P1); … while (1) { a=rand()%(numero-1)+2;//0<a<numero mpz_set_ui(A,a); mpz_set_ui(P1,...

javascript,if-statement,for-loop,primes

You're having unexpected results because you're changing the value of i in PrimeTest3. if(num % i === 0 && PrimeTest3(i)){ // i changed in PrimeTest3 // now i is not what it was when originally passed in PrimeTest3 console.log('this passed the test:' + PrimeTest3(i)); A fix would be to change:...

You do not need to countPrimes separately. Enough to remove and will work: let isPrime n = let rec check i = i > n/2 || (n % i <> 0 && check (i + 1)) check 2 let nums = [ 16; 17; 3; 4; 2; 5; 11; 6;...

python,algorithm,primes,prime-factoring

Here's one way: def largest_primes_under(number, cap): n = cap - 1 while number and n >= 2: if all(n % d for d in range(2, int(n ** 0.5 + 1))): yield n number -= 1 n -= 1 Demo: for p in largest_primes_under(10, 10**9): print(p) Output: 999999937 999999929 999999893 999999883...

Not actually sure why you expect higher performance for much the same problem. Rather than divide, a sieve approach would take each prime, mark all its multiples as having itself as the lowest prime factor, unless already marked. int lpf[MAX] = {}; int primes[MAX_PRIME]; for(int i = 0; i <...

Every time you call asalmi, you set a local variable asayac to 0. This should be a static variable, not a local one.

This comes up from two parts of the code. Firstly, factorize 1 is [1]. Secondly, since x is always divisible by itself, your very final call will always have w == x, so the recursion will be w:(factorize (w `div` w)) which is always w:(factorize 1). To solve this, you...

New Answer: With the change in your code you will now loop through all number. The problem with it now is that once you find a non prime number you will never reset primeEval and because of that you will never capture another prime number If you change your code...

I urge you to use a different algorithm, such as the Sieve of Eratosthenes discussed in the paper by Melissa O'Neill, or the version used in Math.NumberTheory.Primes from the arithmoi package, which also offers an optimized prime counting function. However, this might get you better constant factors: -- is a...

python,loops,sum,primes,logarithm

Although your program is quite chaotic (and the way to determine whether the number is prime is far from optimal, there is probably one mistake). log_of_prime_sum += log_of_prime_sum+float(log(2.0)) += means that you "increase" the variable with the operand, so you state: log_of_prime_sum = log_of_prime_sum+log_of_prime_sum+float(log(2.0)) A way to prevent such errors...

java,model-view-controller,primes

Suppose current is 7 when getNextValue() is invoked. Then newLatest is set to 8. isPrime(8) is obviously false, so then you increment newLatest, making it 9. You assign it to current and return it. This makes 9 the next number after seven, regardless of whether it is prime or not....

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...

Basically if a number q is prime then fermat theorem states that a(q - 1) = 1 (mod q) where a and q are co-prime. So basically the while loop is just calculating the some random number to the power val-1 and also taking the modulo val. If the end...

ruby,algorithm,primes,prime-factoring,factorization

You need to break the $primes.each loop as soon as you find a factor, or it'll complete the loop each time. while !($primes.include?(num)) $primes.each do |x| if num % x == 0 then $factors.push(x) num /= x break end end end $factors.push(num) P.S: I've just kept to the algorithmic side...

It is if (quotient !== math.floor(quotient)) an extra ), and it is Math.floor, uppercase M.

Few points: Once you return is executed, the value it is applied to is returned to whoever called the function and the code after return never executes. You're shadowing the built-in function list() which returns a new list by calling a local variable list. The list is constantly reconstructed by...

You should only pair-up the adjacent primes: (define (stream-zip s t) (cons-stream (list (stream-car s) (stream-car t)) (stream-zip (stream-cdr s) (stream-cdr t)))) Then you keep only the pairs of twins out of all adjacent pairs: (define (twin primes) (stream-filter ... (stream-zip primes (stream-cdr primes)))) ...

list,haskell,list-comprehension,primes

Since this sounds like a fun programming exercise, I will give a hint rather than a complete solution. Here's a template to get you started: [findPair n | n <- [2,4..]]. You can also implement findPair with a list comprehension (plus head -- which is not recursive -- if you...

algorithm,primes,enumeration,factors

We can merge streams of multiples, produced so there are no duplicates in the first place. Starting with the list [1], for each unique prime factor p we multiply the list iteratively by the prime factor k times (where k is the multiplicity of p), to get k new lists,...

python,sequence,primes,collatz,memorization

Your existing code is incorrectly indented. I assume this task is a homework task, so I won't post a complete working solution, but I'll give you some helpful snippets. First, here's a slightly more efficient primality tester. Rather than testing if all numbers less than a are factors of a,...

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...

algorithm,scheme,time-complexity,primes,sicp

Your long ans short questions are actually addressing two different problems. EX 1.23 is problem(below), why the (next) procedure isn't twice faster than (+ 1)? You provide two possible reasons to explain the relative lack of speed up (and 30% speed gain is already a good achievement): The apparent use...

I did sthg like this; I write two for loop to scan both side, and a prime method to find prime numbers. public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int minPrime = 0; int maxPrime = 0; System.out.println("Please give a number "); int number = scanner.nextInt();...

I see some errors: You need to convert your user input to an int, plus you need to move the else: clause to beneath your for-loop instead of beneath your if-statement. The following code works for what you want: p = int(input("Enter a potential prime.")) for n in range (2,p):...

it keeps returning 1. upto() is defined to return the left hand side. In general, a method returns the value of the last statement that was executed--return statements are not required. The last statement in primeMover() is the method call 1.upto(). Note that a block is similar to a...

Your is_prime function seems to incorrectly reuse the variable n in these lines: n = int(n**0.5)+1 for i in range(2,n): if n % i == 0: You might consider using more descriptive names, such as factor_limit for example....

Use the length of the prime array as the looping condition of your for loop, not the number you're testing. function prime(nth) { var arr = [2]; var isPrime = true; for(var i = 3; arr.length <= nth; i++) { isPrime = true; for(var j = 2; j < i;...

You're right, your code seems to be having difficulty as soon as it gets beyond the small_primes table. Looking more closely, there's an error here: for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False You want to return...

c#,for-loop,numbers,primes,do-while

Try this with no bool variable!!!: static void Main(string[] args) { for (int x = 2; x < 10000; x++) { int isPrime = 0; for (int y = 1; y < x; y++) { if (x % y == 0) isPrime++; if(isPrime == 2) break; } if(isPrime != 2)...

Problem is with your Primality Testing algorithm , You cannot determine a number is prime or not until you divide it by all the numbers in the range [2,Sqrt(n)] In line "if(p == 2)" you are assuming that it wont be divided by any number later on in the range...

Making minimal changes to your code, but, as commenter said, adding termination logic: func nthPrimeNumber(n: Int) -> Int { var prime: Int var divisor: Int var isPrime: Bool var counter = 0 for (prime = 2; prime <= 50 && counter < n; ++prime ) { isPrime = true; for...

java,math,numbers,logic,primes

You first need to parse the string you want (3,6,86,13) for example. For this problem, you can use a regexp (now you have two problems (-:). See http://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html. Your regexp needs to parse a parens, following by some digits, then maybe a comma and some more digits multiple times, then...

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...

Your functions are not equivalent. In the first function, the list of candidates goes to n, and the filter function also uses n for remainder calculation. The second function, however, also uses n for remainder calculation, but the candidates list goes to sqrt(n) instead. To make the second function equivalent,...

Yes, this method can be used in cryptography. RSA encryption involves the finding of huge prime numbers, sometimes on the order of 1024 bits (about 300 digits). The security of RSA depends on the fact that factoring a number that consists of 2 of these prime numbers multiplied together is...

Your getPrime() method is nearly right for 5 < N < 19. It won't work for N = 19 because the largest possible long value is 9223372036854775807 which is 19 digits long. The reason it doesn't quite work for values lower than 19 is that it can produce numbers with...